KMP字符串
给定两个字符串,模式串S和模板串P,求P在S中出现的首字母下标。
算法1
(暴力枚举)
暴力求解思路 以S[i]作为匹配起点,向后依次与P匹配,若匹配成功,输出i;否则失配,P向后移动一格
继续与S匹配(即以S[i+1]作为起点与P匹配)
时间复杂度 O(n^m)
C++ 代码
#include<cstdio>
const int Max_M = 1e5 + 10;
const int Max_N = 1e6 + 10;
int m, n;
char p[Max_M], s[Max_N];
int main()
{
scanf("%d",&m);
getchar();
scanf("%s",p+1);
scanf("%d",&n);
getchar();
scanf("%s",s+1);
for( int i=1; i+m-1<=n; i++ )
{
int t = i; //以t作为起点与P匹配
bool flag = true;
for( int j=1; j<=m; j++ )
{
if( p[j]!=s[t++] )
{
flag = false;
break;
}
}
if( flag ) printf("%d ",i-1);
}
puts("");
return 0;
}
算法2
kmp
暴力枚举的思想用到了一个信息
以S[i]作为起点与P失配/匹配
kmp用到了额外的一个信息
如果以S[i]为起点与P[j+1]失配,说明S[i~i+j-1]与p[1~j]匹配
思路
- 前置知识
2.核心思想 当P在P[j+1]与S失配,让P移动至以j为结尾的最大前缀处继续与S匹配。
3.个人理解 通过预处理每次快速找到: 下一个可能匹配的位置在哪里?
4.理解nxt[] 最长且相等的真前缀与真后缀的长度
举例
P = AABAAA
S = AABAABAAA
P与S在P的末尾失配 即
j
AABAAA
AABAABAAA
i
按照暴力思想,我们要将 i<-i+1, j <- 0 从头再来, 可以发现下一次可能的匹配在 ----
j
AABAAA
AABAABAAA
i
而kmp的思想是在第一次失配时,既然p[1~j]与s[i~i+j-1]匹配(这里i=1),说明p[1~j]的真后缀(这里
AABAA的前缀函数值为2)即p[j-2+1 ~ j ]与s[i+j-2 ~ i+j-1]是匹配的, 并且真前缀 = 真后缀即
p[1~2] = p[j-1 ~ j] , 所以p[1~2]必定与s[i+j-2 ~ i+j-1]匹配,那么我们以可让 j 退回到 2 与
i+j 继续判读j+1是否与s之后的符号匹配。
nxt数组的求解过程
如果观察实现代码,我们会惊讶的发现其过程和P与S匹配的过程几乎一模一样,就好像
用P匹配自己。而唯一的不同是i从2开始而不是从1开始。而这唯一的不同说明求nxt的过程不是
用P匹配自己的过程,实际上是用p[1~j+1]试图匹配p[i-j+1,i]。如果试图失败,就用kmp思想回退
下一个可能匹配的j的位置(向前同样利用nxt[]回退)。也就是说nxt数组是求s[1~i]的真前缀与真后缀的
匹配。
为什么要用真前缀与真后缀匹配的最大长度?为什么i=1开始就能保证是真后缀?这些答案可以在模拟
与手写中得到答案。(我也不会严格证明-.-)
时间复杂度 O(m)
y总分析 外层循环m次,我们观察循环内部每次j++一次/0次,也就是j在i循环m次过程中最多自增
m次,所以while循环j最多减m次(j>0)。所以总的时间复杂度时间上是O(m)的。
关键伪码
while( j>0 && 下一个字符(p[j])与s[i]失配 )
j通过nxt数组跳到下一个可能匹配的位置(这里是下一个的第一个)
C++ 代码
#include<cstdio>
const int Max_N = 1e5 + 10, Max_M = 1e6 + 10;
int n, m;
char p[Max_N], s[Max_M];
int nxt[Max_M];
int main()
{
scanf("%d%s%d%s",&n,p+1,&m,s+1);
//构造nxt[]
for( int j=0, i=2; i<=n; i++ )
{
while( j && p[j+1]!=p[i] ) j = nxt[j];
if( p[j+1]==p[i] ) j++;
nxt[i] = j;
}
for( int j=0, i=1; i<=m; i++ )
{
while( j && p[j+1]!=s[i] ) j = nxt[j];
if( p[j+1]==s[i] ) j++;
if( j==n ) //全部匹配
{
printf("%d ", i - n);
j = nxt[j];//匹配完毕 下一个字符无 所以必然会失配 直接跳到下一个可能匹配的位置
}
}
printf("\n");
return 0;
}