POJ.2752 Seek the Name, Seek the Fame

1.Problem
http://poj.org/problem?id=2752

2.Idea
calculate all prefix&suffix by KMP.

3.Source

 string s;  
 int nextarray[400005];  
 void getnext(string &str)  
 {  
      memset(nextarray, 0, sizeof(nextarray));  
      int j = -1, k = 0;  
      nextarray[0] = -1;  
      while (k < str.size())  
      {  
           if (j == -1 || str[j] == str[k])  
                nextarray[++k] = ++j;  
           else  
                j = nextarray[j];  
      }  
 }  
 void solve()  
 {  
      getnext(s);  
      int cur = s.size();  
      vector<int> ans;  
      while (cur > 0) {  
           ans.push_back(cur);  
           cur = nextarray[cur];  
      }  
      sort(ans.begin(), ans.end());  
      for (int i = 0; i < ans.size(); i++) {  
           cout << ans[i] << " ";  
      }  
      cout << endl;  
 }  
 int main()  
 {  
      while (cin >> s) {  
           solve();  
      }  
      return 0;  
 }