kmp

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// 构建 KMP 算法的 next 数组
vector<int> build_next(string pattern) {
    vector<int> next(pattern.size(), 0);
    int i = 1;
    int pattern_len = 0;
    while (i < pattern.size()) {
        if (pattern[i] == pattern[pattern_len]) {  //當匹配的時候
            pattern_len++;
            next[i] = pattern_len;
            i++;
        } else {
            if (pattern_len != 0) { //當不匹配，而且pattern_len != 0， 所以 pattern可以回退回去
                pattern_len = next[pattern_len - 1];
            } else {  //當pattern_len=0，而且pattern[i]!=pattern[pattern_len]，這時候只能給next[i]=0，然後i++ 繼續往前探索。
                next[i] = 0;
                i++;
            }
        }
    }
    return next;
}

// 使用 KMP 算法在文本中查找模式字符串
int kmp(string sentence, string pattern) {
    vector<int> next = build_next(pattern);
    int i = 0, j = 0;
    while (i < sentence.size()) {
        if (sentence[i] == pattern[j]) {
            i++;
            j++;
        }
        else if (j > 0) {    //當 sentence[i] != pattern[j] ，但是 j>0，所以表示 j 可以回退回去。
            j = next[j - 1];
        }  
         else { //當i=0, sentence[i]!=pattern[j]，這時候沒辦法，一定要 i++，因為j一定要從頭算起，不能 skip j++;
            i++;
        }

         if (j == pattern.length()) { //如果 j 跑完了整個 pattern， 表示匹配了所有 pattern的文字，所以可以return j 這個長度
            return j;  // 返回匹配的长度
        }
    }
    return j;  // 返回最长匹配的长度
}
int main() {
    string sentence, pattern;
    while (cin >> sentence) {
        pattern = sentence;
        reverse(pattern.begin(), pattern.end());
        int match_len = kmp(sentence, pattern);
        cout << sentence + pattern.substr(match_len) << endl;
    }
    return 0;
}