[POJ][2752][KMP] Seek the Name, Seek the Fame

题目大意

---

思路

---

代码

---

#include
#include
using namespace std;
#define P_SIZE 1000000
int next[P_SIZE+2],res[P_SIZE];
char P[P_SIZE+2];
//P是模式串。
void COMPUTE_PREFIX_FUNCTION(char P[])
//对next[]进行赋值。 
{
    int m=strlen(P+1);
    next[1]=0;
    for(int k=0,q=2;q<=m;q++)
    {
        while(k>0&&P[k+1]!=P[q])
            k=next[k];
        if(P[k+1]==P[q])
            k++;
        next[q]=k;
    }
}
int main()
{
    while(~scanf("%s",P+1))
    {
        COMPUTE_PREFIX_FUNCTION(P);
        int total=0,len=strlen(P+1);
        res[total++]=len;
        for(int i=len;next[i]!=0;i=next[i])
            res[total++]=next[i];
        for(int i=total-1;i>=0;i--)
            printf("%d%c",res[i],i?' ':'\n');
    }
}

后记

---