qq网站安全认证怎么做,现在o2o的平台有哪些,互联网推广是什么工作内容,wordpress数据管理系统文章出处#xff1a;极客时间《数据结构和算法之美》-作者#xff1a;王争。该系列文章是本人的学习笔记。 KMP#xff0c;是三个作者#xff08;D.E.Knuth#xff0c;J.H.Morris和V.R.Pratt#xff09;的简称。 KMP算法和BM一样#xff0c;也是一个字符串匹配算法。…文章出处极客时间《数据结构和算法之美》-作者王争。该系列文章是本人的学习笔记。 KMP是三个作者D.E.KnuthJ.H.Morris和V.R.Pratt的简称。 KMP算法和BM一样也是一个字符串匹配算法。其核心思想和BM也类似查找规律减少当发生字符不匹配的时候回退的长度和次数减少比较次数降低时间复杂度。 文章内容依然主要来自极客时间的算法专栏。同时参考了知乎文章。
1 字符串匹配是什么
字符串匹配就是想看看一个字符串在另一个字符串中的位置。例如查找字符串ababacd在字符串ababaeabac中出现的位置。这就是字符串查找。 在A中查找BA称为主串B称为模式串。 Aababaeabac Bababacd 一般的查找方法是从第0位开始一一匹配字符。当找到第5位的时候发现字符不匹配。这时候从A的第1位开始与B重头开始一一匹配。当匹配到B串末尾则匹配成功。 public static int indexOf(String a,String b){int idx -1;int n a.length();int m b.length();int i0;while(in){int j 0;int pos i;while(posn jm a.charAt(pos)b.charAt(j)){pos;j;}if(jm){idx i;break;}else{i;}}return idx;}2 这里介绍几个概念。 当查找匹配到不相同的字符的时候在主串中的那个字符成为坏字符。 已经匹配的部分成为好前缀。 字符串前缀子串一个字符串S的前缀子串是指从下标0开始形成S的不同子串。例如SababaS的前缀子串有aababaabab。 字符串后缀子串一个字符串S的前缀子串是指以最后一位为结尾形成S的不同子串。例如SababaS的后缀子串有a,ba,aba,baba。 可匹配子串是指长度相等的前后缀子串相等。例如上个例子中的子串’a’,‘aba’。就是可匹配子串 最长可匹配子串在可匹配子串中找长度最长的子串。上个例子中是’aba’。 最长可匹配前缀子串和最长可匹配后缀子串虽然最长可匹配子串是相同的但是前缀子串和后缀子串的起始位置和结束位置不同。例如上个例子中最长可匹配子串’aba’作为最长可匹配前缀子串起止的位置是0和2最长可匹配后缀子串的位置是2和4。为什么这么关心位置在下面有介绍。 在减少移动次数的过程中我们关心最长可匹配前缀子串C的终止位置x。下面描述中将用C表示最长可匹配前缀子串。
前缀子串后缀子串是否匹配是否CC的终止位置aa是否abba否否abaaba是是2ababbaba否否
3 尽可能少移动
3.1目标是主串位置不动 是不是能够减少移动次数呢可不可以保持主串中的位置不动只移动模式串例如下面这样。 ababaeabac ababacd 因为移动模式串已经匹配的部分ababa就需要前缀子串与后缀子串能匹配得上还要尽可能长也就是上面概念中提到的最长可匹配前缀子串C。 从图中看到用模式串中ababa的前缀子串去匹配主串中ababa的后缀子串。为了不会移动的过头这个匹配还需要使用最长的子串。例如下面这个就不可以。虽然也是匹配子串但是向右移动的更多了可能会错过某些匹配。 ababaeabac ababacd
3.2
这里发现字符串前缀子串和后缀子串匹配完全可以在模式串内进行与主串无关。如果我们暴力枚举求字符串ababa的最长可匹配前缀子串算法复杂度必将很高没有什么改进之处。 我们可以假设如果已经提前知道ababa的最长的那个可以和后缀匹配的前缀子串“aba”并且知道C的终止位置是2数组下标。那模式串的下标就可以直接移动下标3了。
4 模式串求next数组
我们假设把ababa的最长可匹配前缀子串的终止位置是2存在一个数组中这个数组是next数组称为失效函数。 我们假设在模式串“ababacd”的每一个位置都可能发生不匹配则需要求模式串每个子串和本身的next数组值。 next数组下标表示模式串每个子串的结尾下标位置。值表示C字符串的终止位置。 next数组也被成为失效函数。 例如模式串ababacd next数组值为下表。
发生不匹配时候已经匹配好的字符串结尾下标C的结尾下标值a0-1next[0]-1ab1-1next[1]-1aba20next[2]0abab31next[3]1ababa42next[4]2ababac5-1next[5]-1
求next数组的值可以使用动态规划的思想。 假设next[i-1]k。如果模式串S的k1的字符与S的i是相同的则next[i]k1。例如上个表格中next[2]0而且S.charAt(01)S.charAt(21)所以next[3]1。
如果模式串S的k1的字符与S的i是不同的说明字符串[0,i-1]的最长可匹配前缀子串C不可用。接着查找次长是不是满足条件。为什么查找次长因为想要利用之前已经计算的结果。否则就是从头开始计算了。也就没做什么优化了
现在需要证明S[0,i-1]的次长可匹配前缀子串 S[0,k]的最长可匹配前缀子串。
S[0, i-1] 的次长可匹配前缀子串X的前缀、后缀一定在S[0,k]范围内而且是S[0,k]的前缀、后缀那么S[0,k]的最长可匹配前缀子串S[0,i-1]的次长可匹配前缀子串。
如果xk可以推出 S[0,x]长度S[0,k]的长度而且S[0,x]还是S[0,i-1]的可匹配前缀子串,那么S[0,x]应该是S[0,i-1]的最长可匹配前缀子串。这与S[0,k]是最长可匹配前缀子串矛盾。这证明了xk。
进一步因为xk要想找到S[0,i-1]的次长可匹配前缀子串也就是要在S[0,k]找最长可匹配前缀子串。
例如对于对子字符串 abababzababab 来说 前缀有 a, ab, aba, abab, ababa, ababab, abababz, … 后缀有 b, ab, bab, abab, babab, ababab, zababab, … next[13]6。“ababab” 是最长可匹配前缀子串abab是次长可匹配前缀子串。
因为可匹配前缀子串位置从下标0开始的所以对于同一个字符串的次长可匹配前缀子串一定是最长可匹配前缀子串的一部分所以abab 是 “ababab” 的子串。
又因为abab是可匹配子串所以abab 一定是 “ababab” 的前后缀也就一定是“ababab” 的最长可匹配子串。假设abab 不是“ababab” 的最长可匹配子串那对于“abababzababab”的次长子串一定是其他子串而不是abab。
所以“ababab”的最长可匹配前缀子串的终止位置“abababzababab”次长可匹配前缀子串的终止位置。也就是代码knext[k]。
继而继续判断S[k1]是不是和S[i]相同。
public class KMP {// b 表示模式串m 表示模式串的长度private static int[] getNexts(char[] b, int m) {int[] next new int[m];int k -1;next[0] -1;for(int i1;im;i){while(k!-1 b[k1]!b[i]){k next[k];}//假设next[i-1]k,如果模式串S的k1的字符与S的i是相同的if(b[k1] b[i]){k;}next[i] k;}return next;}// a, b 分别是主串和模式串n, m 分别是主串和模式串的长度。public static int kmp(char[] a, int n, char[] b, int m) {int[] next getNexts(b,m);int j 0;for(int i0;in;i){//当字符不匹配的时候将模式串的指针回退到最长可匹配前缀字符的结束下标位置while(j0 a[i]!b[j]){j next[j-1]1;}//字符匹配的时候if(a[i]b[j]){j;}if(jm){return i-m1;}}return -1;}public static void main(String[] args){String a abbaabbaaba;String b a;int p kmp(a.toCharArray(),a.length(),b.toCharArray(),b.length());System.out.println(p);}
}
