P3375 【模板】KMP

· · 题解

P3375 【模板】KMP

可以去看一下课程

\red{注意:本代码没有从1开始读入}

Code:

#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;
}