Instantly share code, notes, and snippets.

# fpelliccioni/Length of palindrome around a Center Last active Aug 29, 2015

 #include // 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 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 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 template 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 void test() { test_length_palindrome_around(std::vector{ 1, 1, 1, 1, 5, 6 }); }