java LeetCode题解KMP算法示例

目录

• KMP算法
• 前缀表
• 匹配过程
• next数组
• 初始化
• 示例题目

KMP算法

前缀表

前缀：包含首字母，不包含尾字母的所有子串

后缀：只包含尾字母，不包含首字母的所有子串

最长相等前后缀

例如aabaaf,其最长相等前后缀如下

a 0

aa 1

aab 0

aaba 1

aabaa 2

aabaaf 0

匹配过程

在匹配过程中如果遇到不匹配，就跳到以该位置的前一位置对应的最长相等前后缀为索引的位置继续匹配

next数组

遇到冲突后回退到相应位置（即前缀表）

求next数组的过程：getnext（next，s）

初始化

前缀末尾j初始化为0,next[0]=0

i为后缀末尾

for(i=1;i<s.size();i++)

前后缀不同

连续回退过程(while):j>0 s[i]!=s[j]

这里连续回退

j=next[j-1]:要点 这种回退表示匹配不成功,那么就需要

回到记忆中已经匹配的下一位接着比较

前后缀相同

s[i]==s[j] j++

更新

next[i]=j:即记录相同位数

示例题目

459.重复的子字符串: 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

思路:使用KMP算法求解,这里利用到了next数js组,也就是最长相等前后缀,为什么要找最长相等前后缀呢?因为在有重复子字符串的字符串中,最长相等前后缀除外的那部分,我们可以推导出是这部分组成了整个字符串,所以通过判断原字符串的长度能否整除这部分字符串的长度就可以直接判断了

public boolean repeatedSubstringPattern(String s) {
        int[] next=new int[s.length()];
        getnext(next,s);
        if(next[s.length()-1]>0){//如果为0会导致能整除从而出错
            if(s.length()%(s.length()-next[s.length()-1])==0){
                return true;
         编程   }
        }

        return false;
    }
    public void getnext(int[] next,String s){
        int j=0;
        next[0]=0;
        for (int i = 1; i < s.length(); i++) {
            while(j>0&&s.charKxkWDAt(i)!=s.charAt(j)){
                j=next[j-1];
            }
            if(s.charAt(i)==s.charAt(j)){
          python      j++;
           php }
            next[i]=j;


        }
    }

以上就是Java LeetCode题解KMP算法示例的详细内容，更多关于java KMP算法的资料请关注编程客栈(www.devze.com)其它相关文章！