Noob
0%

寻找子串(Brute Force, KMP and Boyer-Moore)

发表于 更新于 分类于 ，

Brute Force

暴力方法依次遍历原字符串，每次从当前位置开始与待查找字符串比较，如果对应字符串不相等，那么原字符串向后移动一位继续与待查找字符串比较。如果待查找字符串一直到结尾都相等，那么返回原字符串开始比较的位置即可。最坏情况下，每次待查找字符串都便利到最后一个字符时失配，这种情况下时间复杂度为O（n*m）。 

1
2
3
4
5
6
7
8
9
10
11
12
13
public int indexOf(String str, String needle) {
    if(str == null || needle == null)
        return -1;
    for(int i = 0; i < str.length(); ++i) {
        for(int j = 0; i + j < str.length() && j < needle.length(); ++j) {
            if(str.charAt(i) != needle.length())
                break;
        }
        if(j == needle.length())
            return i - j;
    }
    return -1;
}

注意防止原字符串越界

KMP

KMP算法是对暴力求解算法的改进，主要思想为：充分利用之前比较的结果，例如原字符串为”ABCDABCDABD”，待查找字符串为”ABCDABD”，当待查找字符串的最后一个D与原字符串的第二个C失配时，可以利用失配的D前面的AB与原字符串中的AB已经比较过，并且待查找字符串是以AB起始这一事实，直接比较原字符串中的C和待查找字符串中的C，避免再次比较AB。

算法步骤：

  1. 计算待查找字符串的next数组，该数组保存了待查找字符串的前缀信息，数组中的数字表示待查找字符串对应下标发生失配时下一次开始比较的位置。
  2. 和Brute force类似的流程比较
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
public int strStr(String haystack, String needle) {
    if(haystack == null || needle == null) return -1;
    if(needle.length() == 0) return 0;
    int[] next = calNext(needle);
    
    int i = 0;
    int j = 0;
    while(i < haystack.length()) {
        if(j == -1 || haystack.charAt(i) == needle.charAt(j)) {
            ++i;
            ++j;
        } else
            j = next[j];
        if(j == needle.length())
            return i - j;
    }
    return -1;
}

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

Boyer-Moore

待完成：http://blog.csdn.net/appleprince88/article/details/11881323

参考资料

http://blog.csdn.net/v_july_v/article/details/7041827