串

KMP

一、基本概念

主串、子串（模式串）、前缀、后缀、最大公共前后缀长度

子串（模式串）在主串当中的定位操作，称为串的模式匹配。

BF算法或者说暴力算法容易理解，这里不多做介绍。

二、核心思想

当用子串去匹配主串时，挨个字符比较。若某个字符不匹配，言外之意就是该字符之前的所有字符都是匹配的，感觉像是废话，但请牢记这一点。

KMP的本质：若存在最大公共前后缀，就可以将子串的前缀移到后缀位置上，从而减小不必要的匹配次数，提高效率。

需要说明的是，该操作不会漏掉正确结果，因为若中间存在匹配字符串，只能说明你找的不是最大公共前后缀。这里不予证明。

三、前期准备

KMP将子串的前缀移动到后缀位置上，前缀的下一个字符就继续和主串进行匹配。这时有以下几点考虑：

计算机是不能移动子串位置的，但是运动是相对的，通常使用一个下标j来记录前缀下一个字符的位置，通过改变下标j的值，来实现移动字符串的移动。
每次发生冲突都需要计算j的值，有点浪费时间。所以我们可以假设每个字符都有可能发生冲突，提前计算好所有j的取值，存放在和各自字符下标应的数组中，通常取名next数组。这就是典型的牺牲空间换取时间的做法。
上面谈到，发生不匹配字符之前的所有字符都是匹配的。所以在计算next数组时，我们就不需要主串。通常给定子串，我们就可以求出next数组。

所以，KMP的next数组本质上就是求子串每个字符所对应的最大公共前后缀。

四、手工实现

**与很多教材不同，我们的next数组下标从0开始。**这样做有几点考虑：

一般语言：C/C++、Java等，字符串下标都是从0开始，这样做更有利于编程实现。
参考部分408真题，也是从0开始。本人考408
从解决题目角度，只需要多做一步简单的步骤，就可以得到对应于下标1开始的答案。而且个人觉得这样更容易理解

求next数组三板斧：
规定next[0] = -1。代表子串与主串如果首字符都不匹配，就与主串的下个字符匹配，-1是编程时进行判断的标志。
从子串的第二个字符看起，该字符的前面的最大公共前后缀的个数就是next数组的值。
如果题目直接或者间接说，next数组下标从1开始（比如选项中没有出现-1等），就将next数组的所有数字加1

子串（模式串）	next数组
a b a b a a a b a	-1 0 0 1 2 3 1 1 2

五、KMP优化

KMP优化后存放在nextval数组中

子串（模式串）	next数组	nextval
a b a b a a a b a	-1 0 0 1 2 3 1 1 2	-1 0 -1 0 -1 3 1 0 -1

六、代码实现

cpp

#include <iostream>
#include <string>
using namespace std;

// 获取next数组
void getNext(string str, int* next){
	int i = 1, j=0;
	next[0]=-1;
	
	while(i < str.length()){
	    if(j==-1 || 
	    (str[i-1] == str[j] 
	    && i-1 !=j)) {
	        next[i] = ++j;
	        ++i;
	    }
	    else j = next[j];
	}
}

int main()
{
    string str = "ababaaaba";
    int next[20];
    getNext(str,next);
    for(int i =0;i<10;i++){
        cout <<next[i];
    }
   cout << "Hello World";
   return 0;
}

cpp

#include <iostream>
#include <string>
using namespace std;

// KMP优化
void getNextVal(string str, int* next){
	int i = 1, j=0;
	next[0]=-1;
	
	while(i < str.length()){
	    if(j==-1 || 
	    (str[i-1] == str[j] 
	    && i-1 !=j)) {
	        ++j;
	        next[i] = str[i]==str[j]?next[j]:j;
	        ++i;
	    }
	    else j = next[j];
	}
}


int main()
{
    string str = "aaaaaaaab";
    int next[20];
    getNextVal(str,next);
    for(int i =0;i<str.length();i++){
        cout <<next[i]+1;
    }
 //  cout << "Hello World";
   return 0;
}

子串的个数

串（string）：是由零个或多个字符组成的有限序列，又名叫字符串。
子串：串中任意个连续的字符组成的子序列称为该串的子串，空串也属于子串。

n个字符构成的字符串，假设每个字符都不一样，则共有n(n+1)/2+1个字符串
实例应用：若串S=′software′,其子串的数目是()
解析：n(n+1)/2+1=8（8+1）/2+1=37
串中字符出现重复：字符串'wwwpqqpcom'所有非空子串（两个子串如果内容相同则只算一个）个数是（）
答案：50 解析：包含重复子串共：n(n+1)/2+1=10（10+1）/2+1=55，减去重复：2个w，1个ww，1个q，1个.，所以共55-5=50个

串的定位操作通常称为串的模式匹配

串 ​

KMP ​

一、基本概念 ​

二、核心思想 ​

三、前期准备 ​

四、手工实现 ​

五、KMP优化 ​

六、代码实现 ​

子串的个数 ​

串

KMP