KMP字符串

给定一个模式串S，以及一个模板串P，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模板串P在模式串S中多次作为子串出现。

求出模板串P在模式串S中所有出现的位置的起始下标。

输入格式

第一行输入整数N，表示字符串P的长度。

第二行输入字符串P。

第三行输入整数M，表示字符串S的长度。

第四行输入字符串S。

输出格式

共一行，输出所有出现位置的起始下标（下标从0开始计数），整数之间用空格隔开。

数据范围

输入样例：

3
aba
5
ababa

输出样例：`0 2`

思路：1.

求next数组，做此题字母下标从1开始。此数组中的值表示的位置可分出前后缀相等的最大字符串。求next值是在模板串P中求的。定义两个指针i = 2，j = 0,
因为next[1] = 0 不用计算，所以计算next数组时i的初始值是2。每次比较的是p[j + 1] 和 p[i]。如果二者不等，j = ne[j]。反之，j后移　　

具体见下图：


代码：

1 for(int i = 2 , j = 0 ; i <= n ; i ++){ //ne[1] = 0 ,不用算,所以i从2开始
2 
3         while(j && p[j + 1] != p[i]) j = ne[j];  //如果不相等，j往前跳
4 
5         if(p[j + 1] == p[i]) j ++; //相等的话，j后移
6 
7         ne[i] = j;
8     }

求next数组

2.KMP匹配过程。保证j是不等于0的情况下（因为下标都是从1开始，如果s[i]和p[j + 1]不匹配，j往前跳，匹配的话，j后移。由下图可看到完整的匹配过程以及匹配不成功时j指针的跳动。

（j=ne[j]）

代码：

 1 for(int i = 1 , j = 0 ; i <= m ; i ++){
 2 
 3         while(j && p[j + 1] != s[i]) j = ne[j];  //如果不匹配，j往前跳
 4 
 5         if(p[j + 1] == s[i]) j ++; //匹配的话，j后移
 6 
 7         if(j == n){ 
 8 
 9             printf("%d ",i - n );  //如果模板串全部匹配完，输出初始下标
10             j = ne[j]; //此时j到头，j不能再往后走了，那么到下次匹配的时候，j可以最少移动多少呢？ 其实就是j到next[j]的位置。
11 
12         }
13     }

KMP匹配

好了，现在来看看总体代码吧：

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 const int N = 10010 , M = 100010;
 6 
 7 char p[N],s[M];
 8 
 9 int n,m;
10 
11 int ne[N];
12 
13 int main(){
14     cin >> n >> p + 1 >> m >> s + 1;
15     
16     for(int i = 2 , j = 0 ; i <= n ; i ++){
17         while(j && p[i] != p[j + 1]) j = ne[j];
18         if(p[i] == p[j + 1]) j ++;
19         ne[i] = j;
20     }
21     for(int i = 1 , j = 0 ; i <= m ; i ++){
22         while(j && s[i] != p[j + 1]) j = ne[j];
23         if(s[i] == p[j + 1]) j ++;
24         if(j == n){
25             printf("%d ",i - n);
26             j = ne[j];
27         }
28     }
29     return 0;
30 }

View Code