[kuangbin带你飞]专题十六 KMP & 扩展KMP &

题目

思路

• 看到前后缀就想到kmp了
• 要求的是字符串的所有前后缀相同的长度
• KMP的next求解的时候，如果P[k]!=P[j]，就令k=NEXT[k]，这样找到的k之前的字符串仍然是与后缀相等的前缀（但是变短了）。
• 最后得到的next数组，next[k]储存的是满足条件的最长前缀的长度，那么满足条件的前缀只需要遍历k = next[k]，直到长度为0就行了。

AC代码

#include<iostream>
#include<stack>
using namespace std;
const int MAXN=10000002;

string P;
string T;

int NEXT[MAXN];
int plen,tlen;
void getNEXT(){
    NEXT[0] = -1;
    int k = -1 ;
    int j = 0 ;
    while(j<plen){
        if(k==-1||P[k]==P[j]){
            NEXT[++j] = ++k;
        }else{
            k = NEXT[k];
        }
    }
    
}

int main(){
    
    ios::sync_with_stdio(false);
    while(cin>>P){      
        plen=P.length();
        getNEXT();
        
//      for(int i = 0 ; i<=plen;i++){
//          cout<<" "<<NEXT[i];
//      }
        stack<int> S;
        int k = plen;
        S.push(plen);
        while(NEXT[k] != 0){
            k = NEXT[k];
            S.push(k);
    //      cout<<"k"<<k<<"\n";
        }
        int size = S.size();
        while(size--){
            if(size!=0)
                cout<<S.top()<<" ";
            else cout<<S.top();
            S.pop();
        }
        cout<<"\n";
//      P="";
    }
    
    return 0;
}