poj 2752_Seek the Name, Seek the Fame_KMP

lzusa 发布于 2019-05-22 1 次阅读


题目大意

找出一个字符串中既是前缀也是后缀的字串的长度


思路

利用KMP中next数组的种种玄学性质然后递归输出即可


#include 
#include 
#include 
using namespace std;
char a[500000];
int p[500000];
int print(int x)
{
    if (p[x] > -1)
    {
        print(p[x]);
        printf("%d ", p[x]+1);
    }
    return 0;
}
int main()
{

    while (gets(a) != NULL)
    {
        int n = strlen(a);
        int j = -1;
        p[0] = -1;
        for (int i = 1; i < n; i++)
        {
            while (a[j + 1] != a[i] && j != -1) j = p[j];
            if (a[j + 1] == a[i]) j++;
            p[i] = j;
        }
        print(n - 1);
        printf("%d ", n);
    }
    return 0;
}
]]>