KMP算法

kmp_Algorithms.png

/**
 * Date 09/22/2014
 * 
 * @author tusroy
 * 
 *         Do pattern matching using KMP algorithm
 * 
 *         Runtime complexity - O(m + n) where m is length of text and n is
 *         length of pattern Space complexity - O(n)
 */
public class SubstringSearch {

    /**这个是kmp算法的快方法,这个方法核心是这个lps数组记录的就是pattern的前缀和后缀相等的角标
     * Compute temporary array to maintain size of suffix which is same as prefix
     * Time/space complexity is O(size of pattern)
     * 计算临时数组以保持后缀的大小与前缀相同。
     * 时间/空间 复杂性 是 0(n)
     */
    private int[] computeTemporaryArray(char pattern[]) {
        int[] lps = new int[pattern.length];  //一个lps数组来存储前缀和后缀是否相同的下标
        int index = 0;  //初始化一个index下标来记录pattern的开头角标,同时也是记录字符是否相同的指针,用来回退用的!

        for (int i = 1; i < pattern.length;) {  //i从1开始,因为要和index=0角标开始第一次匹配
            if (pattern[i] == pattern[index]) { //如果pattern的第i个字符等于 index字符,
                lps[i] = index + 1;             //那么lps[i]就记录这个字符相同,记录方式为index+1
                index++;                        //因为index角标的值和i角标的值相同,那么两个角标都向后移动一个角标,就++
                i++;
            } else {                            //走到了else语句,就证明pattern[i]不等于patternn[index]
                if (index != 0) {               //首先先判断index是否为0,如果index已经为0了,就证明index不用再回退到lps[index-1]的角标那里了
                    index = lps[index - 1];     //index不为0,那么就回退到index角标的前一位角标所表示的值的位置那里,就是index= lps[index-1]的值
                } else {                        //到else语句就证明了index已经回到了0,那么index已经无法再回退了,那么记录这个字符不相等,不相等用0来记录
                    lps[i] = 0;                 //所以第i角标的值赋值为0
                    i++;                        //然后i++,将i向后移动一位,再和index对比
                }
            }
        }
        return lps;                             //这个lps数组记录的就是pattern的前缀和后缀相等的角标
    }

    /**
     * KMP algorithm of pattern matching.
     * 模式匹配的KMP算法。
     */
    public int KMP(char[] text, char[] pattern) {

        int lps[] = computeTemporaryArray(pattern);//先创建一个lps数组来记录pattern中前缀和后缀相同的角标
        int i = 0;//i代表的是text的角标
        int j = 0;//j代表的是pattern的角标
        while (i < text.length && j < pattern.length) {//循环条件:当i角标没有走到text的末尾并且j加标也没有走到pattern的末尾
            if (text[i] == pattern[j]) {//如果text[i]字符等于pattern[j]字符那么i和j都向后移动一位继续比较是否相同
                i++;
                j++;
            } else {                    //当读到了else的时候就说明了两个字符不相同,
                if (j != 0) {           //首先判断j是否回到了pattern的开始角标(0),如果j不是0
                    j = lps[j - 1];     //那么j就赋值为lps数组中j角标前一个角标的值,这就是这个lps数组存在的价值,有了这个lps数组,j不用再回到0重新和text匹配比较
                                        //可以直接跳过已经匹配成功的字符,
                } else {                //如果j角标已经为0,那么i++,i向后移动一位再和j比较,这时的j为0
                    i++;
                }
            }
        }
        if (j == pattern.length) {      //如果循环结束后,就证明text或者pattern中有一个已经读取到了末尾了,那么我们就可以判断j角标是否等于pattern的长度
                                        //如果长度相等,就证明已经找到匹配的pattern了
            return i - pattern.length;  //返回text中匹配成功的pattern的第一个字符所在的角标
                                        //在这个算法中,i是不断增大的并且是不会回退,所以i是匹配字符串的末端,所以要i-pattern的长度
        }
        return -1;//如果没有匹配成功,则返回-1
    }

    public static void main(String args[]) {

        String str = "abcxabcdabcdabcy";
        String subString = "abcdabcy";
        SubstringSearch ss = new SubstringSearch();
        // boolean result = ss.KMP(str.toCharArray(), subString.toCharArray());
        int result = ss.KMP(str.toCharArray(), subString.toCharArray());
        System.out.print(result);

    }
}

学习来自b站,附B站视频地址,此文章为学习记录,如有侵犯,立即删除,具体思路请看视频
https://www.bilibili.com/video/av3246487/