kmp_vision

kmp算法是字符串匹配效率最高的算法，它的代码简单，但要弄懂代码到底做了些什么，仅看代码来理解还是有些困难。比如说，它是怎么实现把时间复杂度降到o(m+n)的？（m为匹配串的长度，n为源串的长度）比如说，next table是如何建立的？

在充分理解了kmp算法的原理以后，我脑子里出现了一个字符串匹配的动态过程，我突然想到，如果把它可视化了，是不是理解起来就更方便了呢？

基于这个初衷，我做了这一份kmp算法的可视化。使用也简单明了，即开即用，误操作可能性小。

项目地址：点击此处

其中，我实现了

• 展示区域
  • 源串区域
    • 源串下标
    • 源串
  • 匹配串区域
    • 匹配串下标
    • 匹配串
    • next table
    • next table value
• 输入区域
  • 源串输入
  • 匹配串输入
• 匹配过程
  • 自动进行
    • auto start
  • 手动进行
    • start
    • next
• 结果区域
  • result

当然，这份代码的源码实际上写得并不好，我仅仅是实现了自己想要的功能，代码既不优雅，也不具有扩展性和维护性，所以我也真心地希望，觉得这个功能不错的朋友，可以为这份代码提出宝贵的意见，非常非常感激~

我是雅仔，欢迎体验kmp算法的可视化和测试提bug~

1.01 更新

感谢郑林雄同学提的bug，原有算法有一处bug，在求table数组时，前后缀最大公共子串的求法里，当k重置时，应该再次比较字符串是否相等，否则会漏掉一些情况。

现已更正。

1.02 更新

感谢曾雯端同学指出的bug，当清空source再输入的字符串长度小于pattern时，pattern输入减少并没有重置按钮的可用性。

现已修复。