Sunday algorithm ( Fast String Searching )

发表于   |   分类于 ， ，

字符串搜索算法，也称字符串匹配算法，目的是在主串中查找模式串。Sunday 算法的核心思想是：在匹配过程中，当两者不匹配时，尽可能多的跳过字符（以模式串末尾的下一位为匹配点），以进行下一步匹配

分析

第一次，主串和模式串不匹配，下一个匹配点为空格，其在模式串中并没有出现，所以跳过中间这些字符，将模式串移动到 a

第二次，主串和模式串不匹配，下一个匹配点为 e，从后往前在模式串中查找（匹配时，移动最少位，避免出现丢失），找到后进行移动

优化：以 int[256] 来存储模式串中的字符（ 8 位），从前向后遍历（后面相同的字符覆盖前面的，即相当于从后往前在模式串中查找），可以快速判断匹配点是否存在，不需要重复遍历模式串来查找

代码

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
import java.util.Arrays;

public class Solution {

    public static int searchSunday(String father, String son) {

        if (father == null || son == null || father.length() == 0 || son.length() == 0) {
            return -2;
        }

        int flen = father.length();
        int slen = son.length();

        int i = 0;
        int[] c = new int[256];
        Arrays.fill(c, -1);

        for (i = 0; i < slen; i++) {
            c[son.charAt(i)] = i;
        }

        i = 0;
        int len = flen - slen;

        while (i <= len) {

            int fi = i;
            int si = 0;

            while (fi < flen && si < slen && father.charAt(fi) == son.charAt(si)) {
                fi++;
                si++;
            }

            if (si == slen) {
                return i;
            }

            if ((i + slen) >= flen) {
                return -1;
            }

            i += (slen - c[father.charAt(i + slen)]);
        }

        return -1;
    }
}