P3375 【模板】KMP

Code:

CPP

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int l1,l2,nxt[maxn],j = 0;//j -- prefix_len最长相同前后缀长度 
string s1,s2;
int main(){
  cin >> s1 >> s2;//注意:没有从第一个位置开始 
  l1 = s1.size(),l2 = s2.size();
  for(int i = 1;i < l2;i++){//从第二个数开始看   make next
  	while(j>0 && s2[i] != s2[j]) j = nxt[j-1];//不匹配
  	if(s2[i] == s2[j]) j++;//匹配成功
  	nxt[i] = j; 
  }
  j = 0;
  for(int i = 0;i < l1;i++){
  	while(j>0 && s1[i] != s2[j]) j = nxt[j-1];
  	if(s2[j] == s1[i]) j++;//匹配成功 
  	if(j == l2){
  		cout << i+1-l2+1 << endl;
  		j = nxt[j-1];
  	}
  } 
  for(int i = 0;i < l2;i++) cout << nxt[i] << " ";
  return 0;
}