lanqiao oj 1203 小明的字符串

#include<iostream>
#include<algorithm>
#include<cstring>
 
using namespace std ;
const int N = 1e6 +10 ;
char p[N] , s[N] ;
int n , m ;
int ne[N] ;
int main(){
  cin >> s + 1 >> p + 1 ;
  n = strlen(s+1) ;
  m = strlen(p+1) ;
  for(int i = 2 ,j = 0 ; i <= m; i ++){
    while(j && p[i] != p[j+1]) j = ne[j] ;
    if(p[i] == p[j+1]) j ++ ;
    ne[i] = j ;
  }
  int ans = 0 ;
  for(int i = 1 , j = 0; i <= n ; i ++){
    while(j && s[i]!=p[j+1]) j = ne[j] ;
    if(s[i] == p[j+1]) j ++ ;
    ans = max(ans , j) ;
    if(j == m){
      ans = m ; break ;
    } 
  }
  cout << ans << endl ;
}