KMP算法，用java实现的三种方法_kmp算法java代码实现

暴力解决

package 经典算法的实现.KMP算法;

public class 暴力解决 {
    public int strStr(String haystack, String needle) {
        /*
         我们可以让字符串 needle 与字符串 haystack的所有长度为 m 的子串均匹配一次。
         为了减少不必要的匹配，我们每次匹配失败即立刻停止当前子串的匹配，对下一个子串继续匹配。如果当前子串匹配成功，我们返回当前子串的开始位置即可。如果所有子串都匹配失败，则返回 −1。
         */
        int n = haystack.length(),m = needle.length();
        for (int i=0;i+m <= n;i++){
            boolean flag = true;
            for (int j=0;j<m;j++){
                if (haystack.charAt(i+j)!= needle.charAt(j)){
                    flag = false;
                    break;
                }
            }
            if (flag){
                return i;
            }

        }
        return -1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

调库实现

package 经典算法的实现.KMP算法;

public class 调库实现 {
    public int strStr(String haystack, String needle) {
        int res = 0;
        //第一个匹配项的下标（下标从 0 开始）
        /*
        匹配则返回下标，不匹配则返回-1
         */
//        StringBuilder mySB = new StringBuilder();
//        int searchLength = 2*haystack.length() + needle.length();
//        while (mySB.length() < searchLength){
//
//        }
//        if (haystack.indexOf(needle) != -1){
//            return haystack.indexOf(needle);
//        }
//        return -1;
        return haystack.indexOf(needle);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

KMP的实现

package 经典算法的实现.KMP算法;

public class KMP的实现 {
    /**
     *
     * @param haystack  原串
     * @param needle    需要去尝试找索引的匹配串
     * @return
     */
    public int strStr(String haystack, String needle) {
        /*题目为
            在haystackneedle里面找到第一次出现needle的索引位置。
        */
        if (needle.isEmpty()){
            return 0;
        }
        // 分别读取原串和匹配串的长度
        //方便后期的读取，加速处理
        int n = haystack.length(),m = needle.length();
        // 原串和匹配串前面都加空格，使其下标从 1 开始
        haystack = " "+haystack;
        needle = " "+needle;
        char [] s = haystack.toCharArray();
        char [] p = needle.toCharArray();
        // 构建 next 数组，数组长度为匹配串的长度（next 数组是和匹配串相关的）
        int [] next = new int[m+1];
        // 构造过程 i = 2，j = 0 开始，i 小于等于匹配串长度 【构造 i 从 2 开始】
        for (int i = 2,j=0;i<=m;i++){
            //匹配不成功的话，j=next(j)
            while (j>0 && p[i] != p[j+1]){
                j = next[j];
            }
            // 匹配成功的话，先让 j++
            if (p[i] == p[j + 1]) {
                j++;
            }
            // 更新 next[i]，结束本次循环，i++
            next[i] = j;
        }

        // 匹配过程，i = 1，j = 0 开始，i 小于等于原串长度 【匹配 i 从 1 开始】
        for (int i=1,j=0;i<=n;i++){
            //匹配不成功的话，先让j++
           while (j>0 && s[i] != p[j+1]){
               j = next[j];
           }
           if (s[i] == p[j+1]){
               j++;
           }
           if (j == m){
               return i-m;
           }
        }
        return -1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57