首页 > 代码库 > Kmp算法笔记
Kmp算法笔记
最近刷了一个Kmp的题目才发现,自己对Kmp算法只是一知半解,就去复习了一下。
看了几个版本的算法都感觉不太好,算导的代码感觉不够清晰,其他版本的竟然都是从1开始而非大家习惯的0。经历了各种痛苦之后,终于得到的正确的结果。
懒得写过程,直接上代码吧,主要给自己看的。。。
class KMP { public int Match(string target, string pattern) { int n = target.Length; int m = pattern.Length; var next = GetNext(pattern); int i = 0; int j = 0; while (i < n && j < m) { if (j == -1 || target[i] == pattern[j])//理由同上 { i++; j++; } else { j = next[j]; } } if (j == m) return i - j; return -1; } private int[] GetNext(string pattern) { int m = pattern.Length; int[] next = new int[m]; next[0] = -1; //按照算导的理论来说,这里应该是0,但是我们其实使用的是索引而不是偏移量,有所区别,但是道理一样。长度为0时,那么前面的索引值肯定小于0,我们用的是-1,因为方便 int k = -1;//让整个操作过程能够统一,就从-1开始 int i = 0;//可以让i从第二个字符开始匹配 while (i < m - 1) { if (k == -1 || pattern[i] == pattern[k])//全不匹配时,让i后移一个单位,当k为-1时,有一次循环i的值不会变,这里就是一个校正的过程。 { i++; k++; if (pattern[i] == pattern[k])//用于放置aaaaa这种重复时的无效匹配过程,算是一种优化吧。 next[i] = next[k]; else next[i] = k; } else { k = next[k]; } } return next; } }
Kmp算法笔记
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。