String Matching

这里记录下《Introduction To Algorithm》邓俊辉的《数据结构》里字符串匹配的两种方法，一个是朴素字符串匹配，一个是KMP字符串匹配，还有其他两个叫做Rabin-Karp与有限自动机法的就暂时不考虑了，因为KMP算法在时间复杂度上都可以取代二者。（其实是笔者偷个懒，节约时间搞点别的去。）

如下是各个算法的复杂度，其中是模式的长度，是模式的长度。

image.png

字符串匹配的定义

定义：一个长度为的文本（text）和一个长度为的模式，要求出模式在文本内是否出现，以及出现的话在文本中的位置初始位置在哪，通过初始位置和已知的长度那么就能完全确定子串在文本中位置了，这个便是子串匹配问题，例子如下：

image.png

朴素字符串匹配算法：

对字符串匹配做暴力解法，即每一个中的字符，我都会去计算在这里是不是对的上，这个相信大家都有数了。时间复杂度,即文本中的可能有效位置都算一次的长度。
代码如下，在对模式needle是否匹配文本haystack的算法，该算法只计算一次匹配，若匹配上则退出：

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

KMP算法

之前的暴力解法的缺点是什么呢？下例左图可以说明：可以看到，当串在的匹配过程中，最后一个位置不幸未能匹配上，对于暴力解法，之前的匹配信息它是不管的，它继续一步一步的往前移动来匹配，这种拿着头横冲直闯的精神略有点意思，这是好的，我们怎么去点拨他，让他学会总结失败提高效率呢？比如右图，在前四个字母REGR都匹配的情况下，第五个字母没有匹配上，若是他记得自己曾经在第四个位置匹配上了R，二和三位置匹配上的非R字母，那他不就直接把初始位置移动到第三个字符R上不就合理了吗？

这个思想便是利用此前成功比对所提供的信息，在安全的前提下尽可能大跨度地右移模式串。

StringMaching

• 先说几个字符串的函数,定义前缀函数prefix和后缀函数suffix如下，其中substr(0, k)在c++中的意思是起始位置在0，长度为k的子串。

返回字符串S的前k个字符组成的子串
prefix(S, k) = S.substr(0, k) = S[0, k) 

返回字符串S的最后k个字符组成的子串
suffix(S, k) = S.substr(n - k, k) = S[n - k, n)

上面的例子可以看到有：

suffix(prefix(T, i), 4) = substr(T, i - 4, 4) = prefix(P, 4) = "REGR"

推广一下，把匹配的子串长度4改为变量，我们有：

prefix(P, j) = substr(T, i - j, j) = suffix(prefix(T, i), j)

即模式前面长度为的子串（）已经匹配，但是，

此时要利用这一部分匹配好的信息，我们考虑利用这部分匹配好的信息来右移模式到合适的位置，这个移动长度记为，必然，它的大小肯定是小于的，因为直接移动模式到匹配不上的位置是不合理的，中间可能匹配上呢？

于是经适当右移之后，如果模式串能够与的某一（包含的）子串完全匹配，那么必要的条件之一就是满足：

prefix(P, t) = prefix(prefix(P, j), t) = suffix(prefix(P, j), t)

prefix(P, t)即表示模式长度的前缀子串，他等于prefix(prefix(P, j), t),即他是之前已经匹配上的子串prefix(P, j)的前缀，同时又是之前已经匹配上的子串prefix(P, j)的后缀，有suffix(prefix(P, j), t)。

这个必要条件说了一件事：文本不动，模式在处失去匹配（），那么的头部位置在处，此时要右移到某个位置(设为右移 个单元)。那么必然移动之后有prefix(P, j)的最末长度为的子串等于prefix(P, t),又可等价为prefix(prefix(P, j), t)。

pattern

即肯定来自集合：

N(P, j) = { t | prefix(prefix(P, j), t) = suffix(prefix(P, j), t), 0 <= t < j}

可以看出来，集合的构成只跟失配字符位置，还有模式本身有关。

由上图可知，若我们知道,要保证模式串与主串的对齐位置（指针）绝不倒退，同时又不致遗漏任何可能的匹配，必须在集合中挑选最大的。

next[j] = max(N(P, j))

则一旦发现P[j]与T[i]失配，就可以转而用P[ next[j] ]与T[i]继续比对。因此记录一个next数组，其根据模式本身，计算每一个位置失配后，子串里的自匹配的前缀和后缀的最大长度为t。

构造next表

• next[0] = 0：表示模式的第一个字符匹配失败，此时匹配长度为0；
• 已知next[0, j]，如何计算出next[j + 1]? 字符串在j+1的位置处失配，需要看左边挨着的位置失配情况下的移动是什么。

若左边字符j失配，模式子串prefix(P, j)自匹配的前缀和后缀的最大长度为t；
故必有next[j + 1] <= next[j] + 1，也就是模式子串prefix(P, j+1)比prefix(P, j)最多增加一个字符使得自匹配的前缀和后缀的最大长度为t+1。
当P[j] = P[ next[j] ] 时，必然有 next[j + 1] = next[j] + 1。右下图可知这点。

image.png

• 若P[j] != P[t]，即P[j] != P[ next[j] ]，也就是说t处的字符P[t]不等于当前j处的字符P[j]，于是模式P想找的是若t匹配失败时该该去匹配的位置，我们已经假设找到了，就是next[t]啊。

因此只需反复用next[t]替换t，一旦发现P[j]与P[t]匹配（含通配），即可将next[t] + 1赋予next[j + 1]

一个KMP中使用next的实例：http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/

image.png

c++:

class Solution {
public:
    int strStr(string haystack, string needle) {
        int m = haystack.size(), n = needle.size();
        if (!n) return 0; // 空模式
        vector<int> next(n, 0);
        for(int i = 1, len = 0; i < n;) //step1:建立next表，len为模式needle的匹配长度，初始为0
        {
            if (needle[i] == needle[len]) //若匹配上了，next记录上匹配的长度len；
                next[i++] = ++len;
            else if (len) //匹配长度len一直减小直到匹配上或者未匹配（匹配长度为0）
                len = next[len - 1]; 
            else
                next[i++] = 0; //头部不匹配为0，往前移动
        }
        for (int i = 0, j = 0; i < m;) {  //step2:查找子串
            if (haystack[i] == needle[j]) { //若是匹配的，则文本索引i与模式索引j都前进； 
                i++, j++;
            }
            if (j == n) { //模式索引完毕了，返回模式needle的头部位置i-j
                return i - j;
            }
            if (i < m && haystack[i] != needle[j]) { //失配位置j，通过next表中的靠左位置j-1找到下一个匹配位置
                j ? j = next[j - 1] : i++;         //若是模式needle的第一个位置未匹配，那么直接往文本索引的下一位移动去匹配；
            }
        }
        return -1;  //找不到返回-1
    }
};

class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.empty()) return 0;
        if(haystack.empty()) return -1;
        vector<int> pi(needle.size(), 0);
        //KMP-algorithm:
        //Pre-process
        int k = 0, i;
        for(i = 1; i < needle.size(); i++) {
            while(k > 0  && needle[k] != needle[i]) k = pi[k - 1];
            if(needle[k] == needle[i]) pi[i] = ++k;
        }
        k = 0; //模式P上的游标；
        //Matching
        for(i = 0; i < haystack.size(); i++) {
            while(k > 0 && haystack[i] != needle[k]) k = pi[k - 1]; //看左边挨着的匹配位置
            if(haystack[i] == needle[k]) k++;
            if(k == needle.size()) return i - needle.size() + 1;
        }
        return -1;
    }
};

若是打印所有的匹配位置，只需要修改一下便可：
比如：

输入：
ababab
ab


输出：
0 2 4

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;


vector<int> KMP(const string &str, const string &pattern)
{
    vector<int> ans;
    int n = str.size(), m = pattern.size();
    vector<int>  next(m, 0);
    int k = 0;
    for (int i = 1; i < m; ++i) //get next table
    {
        while(k > 0 && pattern[k] != pattern[i]) k = next[k - 1];
        if (pattern[i] == pattern[k])
            next[i] = ++k;
    }
    k = 0;
    for(int i = 0; i < n; ++i)
    {
        while(k > 0 && str[i] != pattern[k]) k = next[k - 1];
        if (str[i] == pattern[k]) k++;
        if(k == m)
        {
            ans.push_back(i - k + 1);
            k = 0;
        }
    }
    if (!ans.empty()) 
        return ans;
    else
    {
        ans.push_back(-1);
        return ans;
    }
}

int main()
{
    string str, pattern; cin >> str >> pattern;
    vector<int> ans = KMP(str, pattern);
    for(auto i: ans) cout << i << " ";
}