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

题目

题目大意

找s1最长前缀等于s2的后缀。

思路

连接s1，s2，利用失败函数next从k=next[plen]，依次k=next[k]，知道k同时小于等于s1，s2的长度。

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 100002;
int NEXT[MAXN];
string P;
string T;
int plen;
int tlen;
void getNEXT(){
    int k,j;
    k = -1;j = 0;NEXT[0] = -1;
    while(j<plen){
        if(k==-1||P[k] == P[j]){
            NEXT[++j] = ++k;
        }else{
            k=NEXT[k];
        }
    }
    
}


int main(){
    ios::sync_with_stdio(false);
    string s1;
    string s2;
    int lenS2;
    int lenS1;
    while(cin>>s1){
        cin>>s2;
        lenS2 = s2.length();
        lenS1 = s1.length(); 
        P = s1 + s2;
        plen = P.length();
        getNEXT();
//      cout<<"查看next"<<endl;
//      for(int i = 0 ;i<plen;i++){
//          cout<<NEXT[i]<<" ";
//      }
//      cout<<endl;
        int k = plen;
        while(k>lenS1||k>lenS2){
            k = NEXT[k];
        }
        if(k!=0){
            cout<<s1.substr(0,k)<<" "<<k<<"\n";
        }else{
            cout<<k<<"\n";
        }
    }
    return 0;
}