KMP的两种写法

KMP算法可以用来匹配模式字符串，或者寻找最小重复单元，比如abcabcabc，最小重复单元就是abc。qweqweqwe，最小重复单元是qwe。寻找最小重复单元就是计算出字符串的最长公共前缀的长度a，如果 a != 0 && len %(len-a) == 0即找到最小重复单元。

详细内容见KMP算法
核心在于next数组的计算，因此列出getNext的不同计算方法。

1、next[i]表示长度为i的字符串最长公共前缀值

public int[] getNext(String b){int len=b.length();int j=0;int next[]=new int[len+1];//next表示长度为i的字符串前缀和后缀的最长公共部分，从1开始next[0]=next[1]=0;for(int i=1;i0开始{//j在每次循环开始都表示next[i]的值，同时也表示需要比较的下一个位置。 这句注释一定要结合上面的说明理解，理解了KMP算法基本也就搞定了。while(j>0&&b.charAt(i)!=b.charAt(j))j=next[j];if(b.charAt(i)==b.charAt(j))j++;next[i+1]=j;}return next;}

2、next[i]表示字符串[0,i]，即下标。

    private void getNext(String s) {int[] next = new int[s.length()];int i = 1,j = 0;while (i < s.length()) {if (s.charAt(i) == s.charAt(j)) next[i++] = ++j;else if (j == 0) next[i++] = 0;else j = next[j - 1];}}

第二种下标的写法比较简洁，next[i]表示字符串 [0,i]的最长公共缀。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！