第三次开 (KMP) 的坑,加油!
这是板子题:
这是板子:
#include<bits/stdc++.h>
using namespace std;
int j,kmp[1000005];
string s,p;
int main()
{
cin>>s>>p;
for(int i=1;i<p.length();i++)
{
while(j&&p[i]!=p[j]) j=kmp[j];
kmp[i+1]=p[i]==p[j]?++j:0;
}
j=0;
for(int i=0;i<s.length();i++)
{
while(j&&s[i]!=p[j]) j=kmp[j];
j+=s[i]==p[j];
if(j==p.length()) printf("%d
",i-p.length()+2);
}
for(int i=1;i<=p.length();i++) printf("%d ",kmp[i]);
return 0;
}
这是笔记:
- (kmp[i]) 表示模式串第 (i) 位失配后,下面应该用模式串的第 (kmp[i]) 位继续进行匹配;
- 初始化默认了 (kmp[0]=kmp[1]=0) ,这是因为如果第 (0) 或 (1) 位都失配了,就一定需要重头再来;
- 初始化 (kmp) 数组时巧妙的三目运算符
kmp[i+1]=p[i]==p[j]?++j:0;
解决了特判问题; - (kmp) 数组匹配的过程相当于自己和自己匹配
(我配我自己); - (i) 是后缀的最后一位, (j) 是能匹配的前缀的最后一位,这就是为什么 (j) 可以循环使用,也是为什么得到的是
kmp[i+1]
而非kmp[i]
,赋的值是++j
而非j
(第 (i) 位其实可以匹配到第 (j) 位); - 输出的是
i-p.length()+2
是因为:(1)p.length()
没有取到最后一位;(2)字符串的第一位为 (0) 而非 (1) 。
结束~