UVA 11475 - Extend to Palindrome(KMP)

UVA 11475 - Extend to Palindrome

題目鏈接

題意：給定一個字符串，問需要補上最少的字符使他變成回文串

思路：KMP，把字符串逆序和原串做匹配，匹配到最後一個字符看匹配了多少個，就是最大重合部分，然後相應輸出即可

代碼：

#include 
#include 
#include 
using namespace std;

const int MAXLEN = 100005;

struct KMP {

    int next[MAXLEN];

    void getnext(char *str) {
	int n = strlen(str);
	next[1] = 0;
	int j = 0;
	for (int i = 2; i <= n; i++) {
	    while (j && str[j] != str[i - 1]) j = next[j];
	    if (str[j] == str[i - 1]) j++;
	    next[i] = j;
	}
    }

    void find(char *T, char *s) {
	int n = strlen(T);
	getnext(s);
	int j = 0;
	for (int i = 0; i < n; i++) {
	    while (j && T[i] != s[j]) j = next[j];
	    if (T[i] == s[j]) j++;
	}
	printf("%s%s\n", T, s + j);
    }
};

KMP gao;
char a[MAXLEN], b[MAXLEN];

int main() {
    while (~scanf("%s", a)) {
	strcpy(b, a);
	reverse(b, b + strlen(b));
	gao.find(a, b);
    }
    return 0;
}