字符串匹配

提起字符串匹配可能更多人会想到 KMP 算法，该算法时间复杂度为 O(m+n)，而且也是我们在学习数据结构过程中最早接触到的比较好的算法。但 KMP 算法需要在模式字符串有关联的情况下，也即模式字符串前后缀字符相似度较高的情况下匹配效率比较高。但是在实际应用场景中模式字符串更多情况下是无规律的，因此在工程应用中字符串匹配问题的解决更多的使用的是 sunday 算法。

sunday 算法较之于 BM 算法最大的不同点在于 sunday 算法在匹配的过程中主串中参加匹配的最末位字符的下一位字符。

• 如果末尾的下一位字符（如该字符为'a'）没有在模式字符串中出现过，则直接跳到'a'的下一位字符开始新一轮的比较
• 如果模式字符串中包含'a'，则将模式字符串中从左到右中最早出现的字符'a'与源字符串中的'a'对应开始新一轮的匹配

我们下边举一个例子来说明 sunday 算法的匹配过程。比如在一个主串"substring searching"中查找模式串"search"。

1. 开始时，将模式字符串和主字符串左侧对齐开始进行匹配

1. 在匹配的过程中发现在第二个字符 e 处出现匹配失败的情况。此时我们关注参与匹配的最末尾字符的下一位即 i，由于模式字符串中并没有 i，因此模式字符串直接跳过一大片，向右移动位数 = 模式字符串长度 +1，也即移动到字符 n 的位置。

1. 在新一轮的匹配过程中发现第一个字符便出现了不匹配的情况。然后我们看到参与匹配的末尾字符的下一位字符为 r，并且 r 存在于模式字符串中因此可以将模式字符串移动 3 位（移动到模式字符串中的 r 和主字符串中的 r 对齐）如下：

1. 在新一轮匹配过程中发现匹配成功，结束匹配返回匹配的位置。

 1class Solution {
 2    //使用sunday算法来求解
 3    public int strStr(String haystack, String needle) {
 4        //边界判断
 5        if(needle.equals("")||needle==null){
 6            return 0;
 7        }
 8        if(haystack==null){
 9            return -1;
10        }
11        char [] haystackArray=haystack.toCharArray();
12        char []needleArray=needle.toCharArray();
13        int haystackLength=haystackArray.length;
14        int needleLength=needleArray.length;
15        //定义偏移数组
16        int move[]=new int[256];
17        //对偏移数组进行初始化工作
18        for(int i=0;i<256;i++){
19            move[i]=needleLength+1;
20        }
21        for(int i=0;i<needleLength;i++){
22            move[needleArray[i]]=needleLength-i;
23        }
24        //模式字符串第一个字符在匹配过程与源字符串对应的未知，j表示当前已经匹配的字符个数
25        int s=0,j=0;
26        //进行匹配
27        while(s<=haystackLength-needleLength){
28            j=0;
29            while(haystackArray[s+j]==needleArray[j]){
30                j++;
31                if(j==needleLength){
32                    return s;
33                }
34            }
35            if(s<haystackLength-needleLength){
36                s+=move[haystackArray[s+needleLength]];
37            }else{
38                return -1;
39            }
40        }
41        return -1;
42    }
43}