03 字符串匹配

28 实现 strStr() (opens new window)

判断一个字符串是不是另一个字符串的子字符串，并返回其位置。

输入一个母字符串和一个子字符串，输出一个整数，表示子字符串在母字符串的位置，若不存在则返回-1。

输入：haystack = "hello", needle = "ll"
输出：2

解析：

​ 解决本题一种简单的思路是暴力匹配：首先将子串和母串左端对齐；然后逐个比较对应的字符，如果发现不匹配则将子串开始匹配位置相对于母串后移动一位，同时将比较指针回溯到子串头部；重复匹配过程，直到找到对应子串，不存在则返回 -1。

class Solution {
public:
    int strStr(string haystack, string needle) {
        int m = haystack.length(), n = needle.length();
        for(int i=0;i+n<=m;++i){
            bool flag = true;
            for(int j=0;j<n;++j){
                if(haystack[j+i]!=needle[j]){
                    flag = false;
                    break;
                }
            }
            if(flag){
                return i;
            }
        }
        return -1;
    }
};

​ 上述方法的比较指针不断回溯的过程会增加时间复杂度，一种优化方法就是 KMP 算法。KMP 算法的核心思想就是通过寻找已匹配部分子串中的相同前后缀，在遇到字符不匹配的情况时，直接将子串从前缀部分移动到后缀，避免比较指针直接回溯到子串头部。

​ 如下例所示，母串和子串在第 8 个字符出现不匹配，下一步匹配操作：如果使用暴力匹配则是将匹配指针回溯到子串头部并往后移动一位再次寻找与母串左端对齐；如果使用KMP算法，可以看到子串已经匹配的相同最长前后缀为ABC，直接将整个子串从前缀位置移动到后缀，一次性移动四位，避免比较指针从头再开始匹配。

原串	暴力匹配	KMP 算法
ABCFABCFABCA	ABCFABCFABCA	ABCFABCFABCA
ABCFABCA	0ABCFABCA	0000ABCFABCA

​ KMP 算法的关键是在子串中找到最长前后缀，这里可以采用动态规划的思想：

​ 设置状态：构建一个数组 next[i]表示子串中对应位置 i 之前的部分串中最长前后缀的长度。

​ 状态转移方程：对于位置 i，如果下一位前后缀相同，更新相同最大前后缀的长度；如果下一位不同，则将向前回溯。

​ 初始情况：如果仅有一个字符不存在前后缀，next[0]=-1 。前缀指针从 -1 位置开始，后缀指针从 1 位置开始遍历子串。

// 计算前缀表 next
void getNext(string needle, vector<int>& next){
    int head = -1;
    next[0] = -1;
    for(int tail = 1; tail<needle.length();++tail){
        // 如果下一位不同，往前回溯，回溯到没有前缀为止(head=-1)
        while(head>-1 && needle[head+1]!=needle[tail]){
            head = next[head];
        }
        // 如果下一位相同，更新相同的最大前缀和最大后缀长，同时移动前缀指针
        if(needle[head+1]==needle[tail]){
            ++head;
        }
        next[head] = head;
    }
}

​ 一个上述计算ABCFABCA前缀表的例子：

next 索引	部分子串	最长前缀最后一个元素的位置 next[i]
0	A	-1
1	AB	-1
2	ABC	-1
3	ABCF	-1
4	ABCFA	0
5	ABCFAB	1
6	ABCFABC	2
7	ABCFABCA	2

class Solution {
public:
	// 计算前缀表 next
    void getNext(string needle, vector<int>& next){
        int head = -1;
        next[0] = -1;
        for(int tail=1;tail<needle.length();++tail){
            // 如果下一位不同，往前回溯，回溯到没有前缀为止(head=-1)
            while(head>-1 && needle[head+1]!=needle[tail]){
                head = next[head];
            }
            if(needle[head+1]==needle[tail]){
                ++head;
            }
            next[tail] = head;
        }
    }

    int strStr(string haystack, string needle) {
        int cur = -1;
        int m = haystack.size(), n = needle.size();
        // 子串为空返回 0 
        if(n==0) return 0;
        // 获取前缀表
        vector<int> next(n,-1);
        getNext(needle,next);
        for(int i=0;i<m;++i){
            while(cur>-1 && haystack[i]!=needle[cur+1]){
                cur = next[cur];
            }
            if(haystack[i]==needle[cur+1]){
                ++cur;
            }
            // 说明=cur移动到needle的最末端，此时i也指向母串中匹配子串的最后一个位置，返回此时匹配子串最左端的位置
            if(cur == n-1){
                return i - cur;
            }
        }
        return -1;
    }
};