KMP 算法

2019-06-22T22:34:00
package com.logi.algorithm;

public class KMPReview {
    public static void main(String[] args) {
        String text = "This a simple example!";
        String pattern = "simple";
        System.out.println(text);
        for (int i = 0; i < new KMPReview().indexOf(text, pattern); i++) {
            System.out.print(" ");
        }
        System.out.println(pattern);
    }

    public void buildMatch(String pattern, int[] match) {
        match[0] = -1;
        int i;
        for (int j = 1; j < pattern.length(); j++) {
            i = match[j - 1];
            while (i >= 0 && pattern.charAt(i + 1) != pattern.charAt(j)) {
                i = match[i];
            }
            if (pattern.charAt(i + 1) == pattern.charAt(j)) {
                match[j] = i + 1;
            } else {
                match[j] = -1;
            }
        }
    }

    public int indexOf(String text, String pattern) {
        if (text.length() < pattern.length()) {
            return -1;
        }
        int[] match = new int[pattern.length()];
        this.buildMatch(pattern, match);
        int t = 0, p = 0;
        while (t < text.length() && p < pattern.length()) {
            if (text.charAt(t) == pattern.charAt(p)) {
                t++;
                p++;
            } else if (p > 0) {
                p = match[p - 1] + 1;
            } else {
                t++;
            }
        }
        return p == pattern.length() ? t - p : -1;
    }
}
当前页面是本站的「Baidu MIP」版。发表评论请点击:完整版 »