Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /////////////////////////////////////////////////// Header
- #pragma once
- #include <iterator>
- #include <utility>
- #include <cassert>
- namespace palindrome_details
- {
- template<class T> using diff = typename std::iterator_traits<T>::difference_type;
- template<class Iter, class BIter>
- diff<Iter> palindrome(Iter left, BIter right, diff<Iter> const n)
- {
- for (auto i = 0; i < n; ++i)
- {
- if (*left++ != *right++)
- {
- return i;
- }
- }
- return -1;
- }
- }
- template<class Iter>
- std::pair<Iter, Iter> palindrome(Iter const begin, Iter const end)
- {
- auto const n = palindrome_details::palindrome(begin, std::reverse_iterator<Iter>(end), std::distance(begin, end) / 2);
- if (n < 0)
- {
- return make_pair(end, end);
- }
- return make_pair(begin + n, end - (n + 1));
- }
- template<class Iter>
- inline bool is_palindrome(Iter const begin, Iter const end)
- {
- return palindrome(begin, end).first == end;
- }
- /////////////////////////////////////////////////// Source
- #include "palindrome.h"
- #define all(c) std::begin(c), std::end(c)
- void test_palindrome()
- {
- cout << "Testing palindrome...\n";
- vector<int> itis = { 2, 3, 5, 7, 5, 3, 2 };
- assert(is_palindrome(all(itis)));
- itis.erase(find(all(itis), 7));
- assert(is_palindrome(all(itis)));
- auto three = find(all(itis), 3);
- *three = 0;
- assert(!is_palindrome(all(itis)));
- auto problem = palindrome(all(itis));
- assert(problem.first == three);
- *problem.second = *problem.first;
- assert(is_palindrome(problem.first, problem.second + 1));
- itis.erase(itis.begin() + 1, itis.end() - 1);
- assert(is_palindrome(all(itis)));
- itis.erase(itis.begin());
- assert(is_palindrome(all(itis)));
- itis.clear();
- assert(is_palindrome(all(itis)));
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement