以下代码相关注释未完善，大体内容如下：
#include <iostream>
#include <vector>
#include <string>
#include <string_view>#define S(X) for (char i : X) {\std::cout << i;\}\class KMP {
public:KMP() = default;~KMP() = default;KMP(const KMP& k) = delete;KMP(const KMP&& k) = delete;// 0 1 2 3 4 5 6// A A B A B A A// 0 1 0 1 0 1 2
private:std::vector<int> generate_next(const std::string& str) {std::vector<int> n(str.size());for (int i = 1, j = 0; i < str.size(); i++) {while (str[i] != str[j] && j > 0) {j = n[j];}if (str[i] == str[j]) {n[i] = ++j;}}return n;}//std::vector<int> generate_next(const std::string c_pair) {// int len = c_pair.size();// std::vector<int> n(len);// int i = 1, j = 0;//// while (i < len) {// if (c_pair[j] == c_pair[i]) {// n[i] = j + 1;// i++;// j++;// }// else if (j == 0) {// n[i] = 0;// i++;// }// else {// j = n[j - 1];// }// }////// S;// return n;//}void better_next(std::vector<int>& n, const std::string& c_pair) {for (int i = 1; i < c_pair.size(); i++) {if (c_pair[i] == c_pair[n[i]]) {n[i] = n[n[i]];}}}public:std::vector<int> search(const std::string& pair, const std::string& want) {std::vector<int> next = generate_next(want);better_next(next, want);std::vector<int> res;for (int i = 0, j = 0; i < pair.size(); i++) {while (j && pair[i] != want[j]) {j = next[j];}if (pair[i] == want[j]) {j++;}if (j == want.size()) {res.emplace_back(i - j + 1);j = 0;}}return res;}};class Manacher {
public:Manacher() = default;~Manacher() = default;Manacher(const Manacher& m) = delete;Manacher(const Manacher&& m) = delete;private:std::vector<int> half_len;private:std::string insert_hash(const std::string& s) {std::string out;out.reserve(s.size() * 3);out += '^';for (char ch : s) {out += '#';out += ch;}out += "#$";//S(out);return out;}
public:void process(const std::string& s) {std::string str = insert_hash(s);half_len = std::vector<int>(str.size());int mid = 0, hr = 0;for (int i = 1; i < str.size(); i++) {int hl = 1;if (i < hr) {hr = std::min(half_len[mid * 2 - i], hr - i);}while (str[i - hl] == str[i + hl]) {hl++;mid = i;hr = i + hl;}half_len[i] = hl;}}bool judge(int left, int right) {return (right - left) <= half_len[right + left - 2];}};int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);KMP k;std::vector<int> index = k.search("wworawotaworiooworia", "wori");for (int i : index) {std::cout << i << ' ';}std::cout << std::endl;Manacher m;m.process("wocoeocliefuckkcuf");std::string_view res_1 = m.judge(3, 5) ? "True" : "False";std::string_view res_2 = m.judge(2, 6) ? "True" : "False";std::string_view res_3 = m.judge(2, 7) ? "True" : "False";std::cout << res_1 << std::endl << res_2 << std::endl << res_3 << std::endl;return 0;}