option=com_onlinejudge&Itemid=8&category=506&page=show_problem&problem=2470" target="_blank" style="">题目链接：uva 11475 - Extend to Palindrome

题目大意：给定一个字符串，输出最少须要加入多少个字符使得字符串变成回文串。

解题思路：以字符串的转置做KMP，然后用原串匹配就可以。最后匹配长度即为反复长度。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 1e5+5;

char s[maxn], t[maxn];

int n, jump[maxn];

void get_jump () {

    int p = 0;

    for (int i = 2; i <= n; i++) {

        while (p && s[p + 1] != s[i])

            p = jump[p];

        if (s[p + 1] == s[i])

            p++;

        jump[i] = p;

    }

}

int find () {

    int p = 0;

    for (int i = 1; i <= n; i++) {

        while (p && s[p + 1] != t[i])

            p = jump[p];

        if (s[p + 1] == t[i])

            p++;

    }

    return p;

}

int main () {

    while (scanf("%s", s + 1) == 1) {

        printf("%s", s+1);

        n = strlen(s + 1);

        for (int i = 1; i <= n + 1; i++)

            t[i] = s[i];

        reverse(s + 1, s + n + 1);

        get_jump();

        int k = find();

        for (int i = k + 1; i <= n; i++)

            printf("%c", s[i]);

        printf("\n");

    }

    return 0;

}