（基础） --- KMP字符串

字符串匹配问题

一些基本的定义
N, M ：字符串的长度
char s[N], p[M]：待匹配串 匹配串
eg: s[N] = “ababa”, p[M] = “aba”
判断 s[N] 中是否有p[M]这个子串，如果有，下标为多少?

解决方法

暴力解决

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5+10, M = 1e6+10;

int n,m;
char p[N],s[M];
    
int main()
{
    cin >> n >> p+1 >> m >> s+1;
    for(int i = 1; i <= m; i ++ ){
        bool flag = true;
        for(int j = 1; j <= n; j ++ ){
            if(s[i + j - 1] != p[j]) {
                flag = false;break;
            }
        }
        if(flag)
        cout<<i - 1<<" ";
    }
}

时间复杂度为O(n*m)

当n、m过大时,会TLE　（ｏｒｚ）

KMP是什么

KMP全称为Knuth Morris Pratt算法，三个单词分别是三个作者的名字。KMP是一种高效的字符串匹配算法，用来在主字符串中查找模式字符串的位置(比如在“hello,world”主串中查找“world”模式串的位置)。

KMP算法的高效体现在哪

高效性是通过和其他字符串搜索算法对比得到的，在这里拿BF(Brute Force)算法做一下对比。BF算法是一种最朴素的暴力搜索算法。它的思想是在主串的[0, n-m]区间内依次截取长度为m的子串，看子串是否和模式串一样(n是主串的长度，m是子串的长度)

next数组（对于匹配串A自我匹配）

在KMP算法中通过next数组来存储当两个字符不相等时模式串应该移动的位数

1. next[i]表示“A中以i结尾的非前缀字串”与“A的前缀”能够匹配的最长长度

next[i] = max{j},其中j<i并且A[i - j + 1, i] = A{1,j]

2. next数组用来存模式串中每个前缀最长的能匹配前缀子串的结尾字符的下标。

next[i] = j 表示下标以i - j + 1为起点，i为终点的后缀和下标以1为起点，j为终点的前缀相等，且此字符串的长度最长。

f数组（对于匹配串A与待匹配串B进行匹配）

1.f[i]表示"B中以i结尾的子串"与"A的前缀"能够匹配的最长长度

f[i] = max{j},其中j<=i并且B[i - j + 1, i] = A[1,j]

KMP的时间复杂度是多少

KMP的时间复杂度是O(n), 证明方法如下。

//kmp两个循环类似,分析一个即可
for i := 0; i < n; i++ { //4. 两个循环的时间复杂度是O(2n),所以KMP的时间复杂度是O(n)
        for j > 0 && s[i] != pattern[j] { 
            j = next[j-1] + 1 //3. 这里j会减值,由于next[j-1]肯定小于j,所以j最多减n次
        }

        if s[i] == pattern[j] {
            if j == m-1 { 
                return i - m + 1 
            }
            j++ //2. 在循环中,每次循环j最多+1,所以j最多加n次
        }
    }

ne数组的求法以及kmp匹配

求ne数组和kmp很相似，相当于自己找自己的匹配串ne[1] = 0;下标从2开始,紧扣定义。

/*
给定一个模式串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

*/ 

#include<iostream>

using namespace std;

const int N = 10010,M = 100010;

int n,m;
char p[N],s[M];
int ne[N];

int main(){
	cin >> n >> p + 1 >> m >> s + 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;
}

转载自orz