gpt4 book ai didi

笔记:KMP的复习

转载 作者:我是一只小鸟 更新时间:2023-08-01 22:31:33 28 4
gpt4 key购买 nike

Record

一个重要的字符串算法,这是第三次复习.

通过总结我认为之所以某个算法总是忘记,是因为大脑始终没有认可这种算法的逻辑(也就是脑回路).

本篇主要讲解从KMP的应用场景,再到算法知识,以及例题.

Main

现有两个字符串 \(A, B\) ,求出 \(A\) 在 \(B\) 中出现的次数。 范围:字符串长度均 \(\leq 1e6 + 10\) .

其实简单来说,KMP就是优化了双重循环,解决字符串的匹配问题.

所以个人总结一下,遇到字符串的题目,如果dp用不了就考虑哈希和KMP 。

数学上从特殊到一般,那么这里我们从暴力到优化.

以 \(A = abab , B = abababaaabb\) 为例,一般做法是双重循环,时间复杂度 \(O(n ^ 2)\) .

我们来看这个具体是怎么实现的.

每次枚举一个初始点,然后一位一位的判断是否相同。如果相同,就继续判断直到;如果不同,就退出并且选择下一个点作为初始点.

首先,如果说判断到第 \(k\) 位发现不对,不是彻底无法挽救的。如果说这个子串从 \(1 .. k - 1\) 的前缀和后缀都没有相同的,比如说这种 \(abcfd\) ,那么判断过的位也不用再判断了,因为往后移一位就都错开了,所以就一直往后推,判断起点是否相同,相同就开始一位一位继续判断。如果说是这种 \(abcabc\) 那就好办了,因为我们可以进行如下的操作.

                        
                          abcabcbdde
abcabcd

                        
                      

这个时候再第七位发现有问题了,是不是全部跳过呢?当然不是.

                        
                          abc|abcbdde
   |abcabcd

                        
                      

再从相同的前缀开始就可以了。只不过显然这个情况下还是匹配不了.

                        
                              for(int i = 1, j = 0; i <= m; i ++ )
    {
        while(j && b[i] != a[j + 1]) j = ne[j];
        if(b[i] == a[j + 1]) j ++ ;
        if(j == n)
        {
            cout << i - n << ' ';
            j = ne[j];
        }
    }

                        
                      

通过这样的思路,只需要每次遍历一遍母串,时间复杂度 \(O(n)\) .

在匹配之前,得要算一下子串中每一位对应的最长的前缀和后缀,记录下前缀的最后一位.

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

                        
                      

例题

周期 。

利用ne数组的性质,马上就可以得到一个字符串 最长 的相同前缀和后缀。观察发现,存在循环节的字符串观察可知:

  • 当第 \(i\) 位存在 \(i \mod{(i - ne_i)} = 0\) ,那么他的循环节一定是 \(i - ne_i + 1 ... i\) ,个数是 \(i / (i - ne_i)\)

这个自己打打草稿就出来了,不多说了.

代码 。

最后此篇关于笔记:KMP的复习的文章就讲到这里了,如果你想了解更多关于笔记:KMP的复习的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com