KMP

KMP"/>

KMP

1.算法介绍
KMP是经典得不能再经典的字符串查找算法。它用来对字符串查找时的时间复杂度的优化，通过预处理减少大部分没必要计算的问题。
2.算法正题
比如
A：aaabsaabssb lena=11;
B：bssb lenb=4;
以下数组下标从1开始
（1）.一般暴力方法：
我们一个一个查找。先声明两个指针变量i，j。
如果A[i+1]==B[j+1]，就i++，j++；
如果不是，就j=1，i=i-lenb+1；
这段代码的意思就是，我们一个一个枚举母串的起点。
显然这样的算法是十分费时的，我们就可以通过KMP来减少处理的次数。
（2）正题：KMP
1.思想：
在我们发现A[i+1]!=B[j+1]时，我们的暴力算法是需要我们再从头到尾扫一遍。很明显不用这样就浪费了我们前面做出的努力。
易得：我们的求解b[1…j]要跟我们的A[i-j+1…i]完全相等。当A[i+1]!=B[j+1]，我们就需要对j做出改变。那么问题来了，我们的j变为多少呢？goodquestion。这就是KMP的核心了。
举例：比如B：acbacaba A：acbacbacbacaba
当j=5，i=5；A[i+1]!=B[j+1]；我们就可以将j变为2而不是0；
这样就会减少j变为1的更多运算。
很显然：我们得到的j’，就是一个该字符串的最大相等前缀和后缀
比如： abab ：j’=2 abbbcdabbbc ：j’=5
我们直接预处理出一个j’数组，在程序运行直接获得就好。
2.预处理数组实现（这是一个在KMP中很重要的点）：
求p[j’]数组：表示没能够匹配，j将要变成的值
原理：
B :ababacd
已经知道p[1-4] ,我们来寻找一下p[5],p[6];
p[1]=0;
p[2]=0;
p[3]=1;
p[4]=2;
因为p[4]=2&&B[3]=B[5]
所以p[5]=p[4]+1;
p[6]?
貌似很棘手啊
我们来想一下p数组的性质，它是用来存储最大相等前缀和后缀的。
求解p[j]我们应该遍历已经找到的p[j’],
根据p[5]=p[4]+1,很多人会想，p[j]=p[j’]+1 &&j’=j-1?这个等式的成立是有条件的，即B[p[j’]]=B[j]
比如 abcabc 如果要达到p[6]=p[5]+1,就需要达到B[6]=B[3].
想到这里问题就比较明朗了，比如找p[6],如果p[5]不能取，那么我们就找p[p[5]].一直找到1为止

void pre()
{p[1]=0;int j=0;for(int i=1;i<len2;i++){while(j>=1&&b[i+1]!=b[j+1]) j=p[j];if(b[i+1]==b[j+1]) j++;//能够匹配了，我们就加上已经匹配好的B[i+1]p[i+1]=j;	}
}

3.KMP内容
有了神器P数组的帮助，我们求解内容其实就跟暴力差不多了，只是在改变j的时候改为P[j]就好。

void kmp()
{int j=0;for(int i=0;i<len1;i++){while(j>=1&&a[i+1]!=b[j+1]) j=p[j];//不能匹配，再次寻找if(a[i+1]==b[j+1]) j++;if(j==len2){cout<<i-j+2<<endl;j=p[j];//继续寻找匹配的}}
}

可以发现的是，这一段代码和上一段代码相似度很高。因为它们两个都是一个寻找匹配的过程，所以大致相同的
3.例题详解
（1）P3375模板题
传送门
题目描述
如题，给出两个字符串s1和s2，其中s2为s1的子串，求出s2在s1中所有出现的位置。

为了减少骗分的情况，接下来还要输出子串的前缀数组next。

（如果你不知道这是什么意思也不要问，去百度搜[kmp算法]学习一下就知道了。）

输入格式
第一行为一个字符串，即为s1

第二行为一个字符串，即为s2

输出格式
若干行，每行包含一个整数，表示s2在s1中出现的位置

接下来1行，包括length(s2)个整数，表示前缀数组next[i]的值。

输入输出样例
输入 #1 复制
ABABABC
ABA
输出 #1 复制
1
3
0 0 1
说明/提示
时空限制：1000ms,128M

数据规模：

设s1长度为N，s2长度为M

对于30%的数据：N<=15，M<=5

对于70%的数据：N<=10000，M<=100

对于100%的数据：N<=1000000，M<=1000000

样例说明：

所以两个匹配位置为1和3，输出1、3

题解
这是一道很基础的模板题，直接上模板就可以了
附上AC代码+注释

#include<bits/stdc++.h>
#define maxn 1000050
using namespace std;
char a[maxn];
char b[maxn];
int p[maxn];
int len1,len2;
void pre()
{p[1]=0;int j=0;for(int i=1;i<len2;i++){while(b[j+1]!=b[i+1]&&j>0) j=p[j];if(b[i+1]==b[j+1])	j++;p[i+1]=j;}
}
void kmp()
{int j=0;for(int i=0;i<len1;i++){while(j>0&&b[j+1]!=a[i+1]) j=p[j];if(a[i+1]==b[j+1]) j++;if(j==len2){cout<<i-j+2<<endl;j=p[j];}}
}
int main()
{cin>>a+1;	//表示字符串首部是a[1]scanf("%s",b+1);len1=strlen(a+1);len2=strlen(b+1);	pre();kmp();for(int i=1;i<=len2;i++)cout<<p[i]<<" ";cout<<endl;return 0;
}

（2）P4391
传送门
题目描述
给你一个字符串，它是由某个字符串不断自我连接形成的。 但是这个字符串是不确定的，现在只想知道它的最短长度是多少.

输入格式
第一行给出字符串的长度,1 < L ≤ 1,000,000.

第二行给出一个字符串，全由小写字母组成.

输出格式
输出最短的长度

输入输出样例
输入 #1 复制
8
cabcabca
输出 #1 复制
3
说明/提示
对于样例,我们可以利用"abc"不断自我连接得到"abcabcabc",读入的cabcabca,是它的子串

个人意见：将“abc”改成“cab”

题解
1.分析
此题做法还是有一点投机的。有关子母字符串，很容易让人想到KMP算法，此题也正是使用这种方法。
p[]:定义字符串b的最大相等前缀和后缀。
x:求解目标，最小子串
分析一下样例，很明显 ：p[x]=0；
p[x+1]=x+1-x=1;
p[n]=n-x;
所以我们就可以根据这个很容易地求到n-p[n]=x;
2.附上AC代码+注释

#include<bits/stdc++.h>
#define maxn 1000050
using namespace std;
char b[maxn];
int p[maxn];
int len;
void pre()
{int j=0;p[1]=0;for(int i=1;i<len;i++){while(j>=1&&b[i+1]!=b[j+1]) j=p[j];if(b[i+1]==b[j+1]) j++;p[i+1]=j;}
}
int main()
{cin>>len;cin>>b+1;//字符串首为b[1];pre();//计算pcout<<len-p[len];return 0;
} 

（3）
P3435 [POI2006]OKR-Periods of Words

传送门

题目描述
A string is a finite sequence of lower-case (non-capital) letters of the English alphabet. Particularly, it may be an empty sequence, i.e. a sequence of 0 letters. By A=BC we denotes that A is a string obtained by concatenation (joining by writing one immediately after another, i.e. without any space, etc.) of the strings B and C (in this order). A string P is a prefix of the string !, if there is a string B, that A=PB. In other words, prefixes of A are the initial fragments of A. In addition, if P!=A and P is not an empty string, we say, that P is a proper prefix of A.

A string Q is a period of Q, if Q is a proper prefix of A and A is a prefix (not necessarily a proper one) of the string QQ. For example, the strings abab and ababab are both periods of the string abababa. The maximum period of a string A is the longest of its periods or the empty string, if A doesn’t have any period. For example, the maximum period of ababab is abab. The maximum period of abc is the empty string.

Task Write a programme that:

reads from the standard input the string’s length and the string itself,calculates the sum of lengths of maximum periods of all its prefixes,writes the result to the standard output.

一个串是有限个小写字符的序列,特别的,一个空序列也可以是一个串. 一个串P是串A的前缀, 当且仅当存在串B, 使得 A = PB. 如果 P A 并且 P 不是一个空串,那么我们说 P 是A的一个proper前缀. 定义Q 是A的周期, 当且仅当Q是A的一个proper 前缀并且A是QQ的前缀(不一定要是proper前缀). 比如串 abab 和 ababab 都是串abababa的周期. 串A的最大周期就是它最长的一个周期或者是一个空串(当A没有周期的时候), 比如说, ababab的最大周期是abab. 串abc的最大周期是空串. 给出一个串,求出它所有前缀的最大周期长度之和.。

输入格式
In the first line of the standard input there is one integer kk (1\le k\le 1\ 000\ 0001≤k≤1 000 000) - the length of the string. In the following line a sequence of exactly kk lower-case letters of the English alphabet is written - the string.

输出格式
In the first and only line of the standard output your programme should write an integer - the sum of lengths of maximum periods of all prefixes of the string given in the input.

输入输出样例
输入 #1 复制
8
babababa
输出 #1 复制
24
题解
1.分析
先翻译一下这道让人无法看懂的题。
给出一个数组，长度为n。
你需要对它的n个前缀进行操作
操作：比如现在我们需要操作前缀i。你需要找出该i字符串的最大周期。并且把n个前缀的最大周期的值加起来。
既然需要加上最大周期，那么怎么求最大周期呢？
如图，每个字符串都可以分为三个小字符串，我们称为1,2,3号；（从左往右的顺序）
当1号3号完全相等时，1和2，或者2和3就构成了一个周期；
最大：也就是1和3越小时周期T就会越大

根据前后相等的性质（1号和3号），我们很自然就想到了KMP中的next数组（我习惯用p数组来表示）。那么怎么求最小呢，我们一直递归下去就好了
放一段伪代码吧；

ll print()
{for(int i=1;i<=n;i++){int j=i;while(next[j]) j=next[j];ans+=i-j;if(next[i]) next[i]=j;//这里是一个优化，相当于以后我在访问next[i]，可以一步到位，有点像并查集的优化//如果这里不优化的化应该会有60分}return ans;
}

2.附上AC代码+注释

#include<bits/stdc++.h>
#define maxn 1000005
#define ll long long int 
using namespace std;
int n;
char a[maxn];
int next[maxn];
void pre()
{next[1]=0;int j=0;for(int i=1;i<n;i++){while(j>=1&&a[i+1]!=a[j+1]) j=next[j];if(a[i+1]==a[j+1]) j++;next[i+1]=j;}
}
ll ans=0;
ll print()
{for(int i=1;i<=n;i++){int j=i;while(next[j]) j=next[j];ans+=i-j;if(next[i]) next[i]=j; }return ans;
}
int main()
{cin>>n;cin>>a+1;//数组首项从a[1]开始pre();cout<<print();return 0;
}