1. KMP

KMP

给予主串S与模式串P，寻找模式串在主串中是否出现过以及出现位置

KMP构造的自动机与字典树类似，但是状态表示不同

KMP自动机中的每个状态代表输入串的后缀是模式串的一个前缀

我们称一个状态的深度为该状态代表的后缀长度，若状态u到状态v满足v的深度=u的深度+1，则称这个转移是u的邻转移

同一个输入串有若干后缀，所以可能符合自动机的多个状态，较短后缀一定是较长后缀的后缀，所以符合状态A的输入串一定符合代表串是A代表串后缀的状态

匹配过程

设主串S：abcxabcdabxabcdabcdabcy，模式串P：abcdabcy

构建Next数组

针对模式串P，我们有一个Next数组，Next[i]指P[0…i]的最长公共前后缀的长度

如例子中P的Next数组为0 0 0 0 1 2 3 0 ，如下表

下标	1	2	3	4	5	6	7	8
字符串	a	b	c	d	a	b	c	y
前后缀	a	ab	abc	abcd	abcda	abcdab	abcdabc	abcdabcy
最长公共前后缀	/	/	/	/	a	ab	abc	/
Next[i]	0	0	0	0	1	2	3	0

让两个指针j，i指向P头，让i逐个移动，与j所指的比较，若不同，则j跳转到该位的前一位Next数组值对应的下标，该位Next数组值为0；若相同，则j向右移动一位，该位Next数组值为移动后的j值（即Next[i]=++j）

性质：i+1-Next[i]为前缀循环节的大小

或把P与S合并成一个串，算出Next数组值，若某位值n等于P的长度，说明找到了和P匹配的字串，因为该处合并串的前后缀相同，该位置向前n长度的字串即为P

在构造Next数组时，假如需要计算Next[i]的值，此时前Next[i-1]位相等，记为len-1，若两侧字串加上第len与第i位，字串仍相等，则Next[i]=len+1，若不相等，则寻找第二长的Next，重复判断直到找到最小的Next(len=0)

搜索模式串

用两个指针指向两串头，逐个匹配，当遇到不同字符时，查看该字符前一个字符对应next数组中的值，让模式串指针跳到该值对应的P的下标位置，继续与主串指针逐个匹配

当找到对应模式串在主串出现时，通过i-len(p)+1计算起始位置

注意：整个匹配过程中主串指针不会后退，只会停留；而模式串指针根据next数组反复横条

板子-1

#include <bits/stdc++.h>
using namespace std;

void Next_pre(string p, vector<int> &Next){
  for(int i = 1,j=0;i<p.size();i++){ // i是当前遍历到的后缀
    while(j&&p[i]!=p[j]) j=Next[j-1]; // 两指针指向不同时按Next中值跳转直到跳到0
    if(p[i]==p[j])j++; // 前后缀一样时，前缀向后移动
    Next[i]=j;
  }
}

int kmp(string s,string p,int begin){ // begin表示从哪里开始匹配
  vector<int> Next(p.size());
  Next_pre(p,Next);
  for(int i = begin,j=0;i<s.size();i++){
    while(j&&s[i]!=p[j]) j=Next[j-1]; // 两指针指向不同时按Next中值跳转直到跳到0
    if (s[i]==p[j])j++; // 前后缀一样时，前缀向后移动
    if (j==p.size()){ // 匹配成功后的操作
    // 该部分操作按题目要求
      return i-p.size()+1;
    }
  }
  return -1;
}
int main(){
  string s,p;
  cin >> s >> p;
  cout << kmp(s,p,0);
  return 0;

}

板子-2

#include <bits/stdc++.h>
using namespace std;
int kmp(string s,string p){
  int n = s.size();
  int m = p.size();
  string mer = p+'#'+s;
  vector<int> Next(mer.size());
  for (int i = 1;i<mer.size();i++){
    int len = Next[i-1];
    while(len&&mer[i]!=mer[len]) len = Next[len-1];
    if (mer[i]==mer[len]){
      Next[i]=len+1;
      if (Next[i]==m){
        return i-m*2;
      }
    }
  }
  return -1;
}
int main(){
  string s,p;
  cin >> s>>p;
  cout << kmp(s,p);
  return 0;

}

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可

红魔咖啡馆

【字符串】KMP

KMP

匹配过程

构建Next数组

搜索模式串

板子-1

板子-2