HDU 2594 Simpsons’ Hidden Talents KMP的next数组应用 - c++编程基础

题意：找到最长的s1的前缀=s2的后缀。

把俩字符串连在一起就跟POJ 2752差不多了，不过得判断下长度。

代码：

/* 
*  Author:      illuz  
*  Blog:        http://blog.csdn.net/hcbbt 
*  File:        hdu2594.cpp 
*  Create Date: 2013-11-28 14:50:47 
*  Descripton:  kmp  
*/  
  
#include   
#include   
  
const int MAXN = 5e5 + 1;  
  
char P[MAXN * 2], s1[MAXN], s2[MAXN];  
int f[MAXN * 2];  
  
void getVal(char* p, int l) {  
    int i = 0, j = -1;  
    f[0] = -1;  
    while (i < l) {  
        if (j == -1 || p[i] == p[j]) {  
            i++; j++;  
            f[i] = j;  
        } else j = f[j];  
    }  
}  
  
int main() {  
    while (~scanf("%s%s", s1, s2)) {  
        strcpy(P, s1);  
        strcat(P, s2);  
        int l1 = strlen(s1), l2 = strlen(s2), l = strlen(P);  
        getVal(P, l);  
        if (f[l] <= 0) puts("0");  
        else if (f[l] >




 l1 || f[l] > l2) {  
            if (l1 > l2)  
                printf("%s %d\n", s2, l2);  
            else  
                printf("%s %d\n", s1, l1);  
        } else {  
            P[f[l]] = 0;  
            printf("%s %d\n", P, f[l]);  
        }  
    }  
    return 0;  
}