二、数据结构7：KMP 模板题+算法模板（KMP字符串）

「爱情、让人受尽委屈。」 2023-10-14 11:13 71阅读 0赞

#### 文章目录 ####

*  算法模板
 *   *  KMP题目模板
 *  模板题
 *   *  KMP字符串
     *   *  原题链接
         *  题目
         *  思路
         *  题解

## 算法模板 ##

### KMP题目模板 ###

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
    求模式串的Next数组：
    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;
    }
    
    // 匹配
    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 ++ ;
        if (j == m)
        {
            j = ne[j];
            // 匹配成功后的逻辑
        }
    }

## 模板题 ##

### KMP字符串 ###

#### 原题链接 ####

[https://www.acwing.com/problem/content/833/][https_www.acwing.com_problem_content_833]

#### 题目 ####

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

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

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

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

第二行输入字符串 P  
。

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

第四行输入字符串 S  
。

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

数据范围  
1≤N≤105

1≤M≤106  
输入样例：

3
    aba
    5
    ababa

输出样例：

0 2

#### 思路 ####

视频讲解：[https://www.acwing.com/video/259/][https_www.acwing.com_video_259]

![在这里插入图片描述][37f2563e2aa249f089bde4139b0dbd9d.png]  
关于next数组：  
![在这里插入图片描述][9ac81486aeaa4e3a9dc03d5cea40c320.png]  
“前缀串=后缀串”  
![在这里插入图片描述][b5b0b30adb7443eebefeb66b1ad6ea22.png]

#### 题解 ####

#include <iostream>
    using namespace std;
    
    const int N = 1e5 + 10;
    const int M = 1e6 + 10;
    
    int n,m;
    char p[N],s[M];
    int ne[N];
    
    int main(){
    	cin>>n>>p+1>>m>>s+1;
    //	p为字符数组，cin>>p+1表示字符数组从第二位开始输入！ 即把p[0]空出来，从p[1]开始输入 
    	
    //	求next数组 
    	for(int i=2,j=0;i<=n;i++){
    		while(j && p[i] != p[j+1]) j = ne[j]; // 在模板串内找前缀串与后缀串相同的位置 
    		if(p[i] == p[j+1]) j++;
    		
    		ne[i] = j;
    	}
    	
    //	KMP匹配： 
    	for(int i=1,j=0;i<=m;i++){
    		while(j && s[i] != p[j+1]) j = ne[j];
    		if(s[i] == p[j+1]) j++;
    		
    		if(j == n){
    			printf("%d ",i-n);
    			j = ne[j];
    		}
    	}
    	
    	return 0; 
    }

[https_www.acwing.com_problem_content_833]: https://www.acwing.com/problem/content/833/
[https_www.acwing.com_video_259]: https://www.acwing.com/video/259/
[37f2563e2aa249f089bde4139b0dbd9d.png]: https://img-blog.csdnimg.cn/37f2563e2aa249f089bde4139b0dbd9d.png
[9ac81486aeaa4e3a9dc03d5cea40c320.png]: https://img-blog.csdnimg.cn/9ac81486aeaa4e3a9dc03d5cea40c320.png
[b5b0b30adb7443eebefeb66b1ad6ea22.png]: https://img-blog.csdnimg.cn/b5b0b30adb7443eebefeb66b1ad6ea22.png