Kmp

· · 个人记录

相关文献

提高一定会出！

定义：

给定一个模式串 p 和一个主串 s。求模式串 p 在主串 s 中出现的位置（简称匹配）。

做法：

我们可以使用两个指针指两个子串位置，一一匹配，但是复杂度为 n \cdot m，我们丢失了之前的信息。

所以我们可以让指针去一个好位置去匹配。

（\text {nex}t_{i} 表示模式串 p_{1,i}中相等后缀最长长度）

如 a a b a中只有一个（a 与 a，aa 与 ba不符）

我们这样匹配最终复杂度为n^2。

next 如果加，最多加1，否则减小，用前面的值算出（有关系的前提是前面必须包含的）。

什么？大佬过于专业，就是指针找下一个，不同就往前找之前找过相同的（学会利用），进可攻，退可守。

next[1]=0;
for(int i = 2,j=0;i<=n;i++){
   while(j&&p[i]!=p[j+1])j=next[j];
   if(p[i]==p[j+1])j++;
   next[i]=j;
}

图片

双指针：i扫描模式串，j 扫描前缀

初始化： next[1]=0,i=2,j=0。

每轮for循环，i向右走一步

1.若p[i]!=p[j+1]，让j回调到能匹配的位置如果找不到匹配的位置，j会跳到0

2.若p[i]==p[j+1]，让j+1，指针匹配前缀的末尾

3.next[i]等于j的值。

那么，引入后。。。（话说我也不懂） 模式串开始与主串匹配：

图

双指针：i扫描模式串，j 扫描前缀

初始化： i=1, j=0

每轮for循环，i向右走一步

1.若s[i]!=p[j+1]，让j回调到能匹配的位置如果找不到匹配的位置，j会跳到0

2.若s[i]==p[j+1]，让j向右走一步

3.若匹配成功，输出匹配的位置。

for(int i = 1,j=0;i<=m;i++){
    while(j&&s[i]!=p[j+1])j=next[i];
    if(s[i]==p[j+1])j++;
    if(j==n)cout<<i-n+1;
}

这时候有三个问题，next有啥用，为啥找前缀和，有啥用？

比方说现在 ab 串中出现了一个 c，为了找到下一个，我们发现之前模式串没有 c ，所以包括 c 之前的所有东西全要忽略，省去时间

本题做到 i 指针往前走，j 来回移动。