Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
#include <iterator>
// Concepts
#define Iterator typename
#define ForwardIterator typename
#define OutputIterator typename
#define BidirectionalIterator typename
#define RamdomAccessIterator typename
#define Integer typename
bool odd(int n) { return n & 0x1; }
template <BidirectionalIterator I, Integer Z>
Z length_palindrome( I first, I last, Z start, Z end )
{
// precondition: start >= 0 &&
// end < std::distance(first, last) &&
// end > start
auto length = end - start - 1;
I left = std::next(first, start);
I right = std::next(first, end);
if ( *left != *right )
{
return length;
}
++right;
length += 2;
while ( left != first && right != last )
{
--left;
if ( *left != *right )
{
return length;
}
++right;
length += 2;
}
return length;
}
template <BidirectionalIterator I, Integer Z>
Z length_palindrome_around( I first, I last, Z center )
{
// precondition: center >= 2 &&
// center < ((std::distance(first, last) * 2 - 2)
auto index = center / 2;
return length_palindrome( first,
last,
index - 1,
index + ( odd(center) ? 1 : 0 )
);
}
#include <iostream>
template <typename Cont>
void test_length_palindrome_around( Cont const& cont )
{
std::cout << "c: " << 0 << " - length: " << 0 << std::endl;
if ( ! cont.empty() )
{
std::cout << "c: " << 1 << " - length: " << 1 << std::endl;
auto centers = cont.size() * 2 - 2;
for (int c = 2; c <= centers; ++c)
{
std::cout << "c: " << c << " - length: " << length_palindrome_around(begin(cont), end(cont), c) << std::endl;
}
std::cout << "c: " << centers+1 << " - length: " << 1 << std::endl;
std::cout << "c: " << centers+2 << " - length: " << 0 << std::endl;
}
}
#include <vector>
void test()
{
test_length_palindrome_around(std::vector<int>{ 1, 1, 1, 1, 5, 6 });
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment