POJ 2752 Seek the Name, Seek the Fame KMP

#include<iostream>
#include<string>
using namespace std;

string s;
int nex[400010];

void getNext()
{
    int i = 0, j = -1;
    int len_s = s.length();
    nex[0] = -1;
    while(i < len_s)
    {
        if(j == -1 || s[i] == s[j])
        {
            j++;           
            i++; 
            nex[i] = j;
        }
        else j = nex[j];
    }
}

void solve(int len)
{
    if(nex[len] > 0)
    {
        solve(nex[len]);
        printf("%d ", nex[len]);
    }
}

int main()
{
    while(getline(cin, s))
    {
        getNext();
        int len = s.length();
        solve(len);
        printf("%d ", len);
        printf("\n");
    }
    //getchar();
    return 0;
}
上一篇:Servlet的细节


下一篇:link链表类实验(多文件模式)