字符串匹配的KMP算法

字符串匹配的KMP算法

实现1-部分匹配表

"部分匹配表"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，
　　－　"A"的前缀和后缀都为空集，共有元素的长度为0；
　　－　"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
　　－　"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
　　－　"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
　　－　"ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；
　　－　"ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；
　　－　"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

部分匹配表

// 计算前缀和后缀相同元素的最大长度
int GetSameCount(const vector<string>& prefix, const vector<string>& suffix)
{
    int max = 0;
    for (int i = 0; i < prefix.size(); i++) {
        auto it = find(suffix.begin(), suffix.end(), prefix[i]);
        if (it != suffix.end()) {
            if (max < prefix[i].size()) {
                max = prefix[i].size();
            }
        }
    }
    return max;
}

// 计算部分匹配表："部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。
vector<int> MatchTable(string src)
{
    vector<int> table(src.size(), 0);
    if (src.empty()) {
        return table;
    }

    vector<string> prefix;
    vector<string> suffix;
    string tmpstr(1, src[0]);
    for (int i = 1; i < src.size(); i++) {
        string prestr = tmpstr;
        tmpstr += src[i];
        
        prefix.push_back(prestr);
        
        for (int j = 0; j < suffix.size(); j++) {
            suffix[j] += src[i];
        }       
        suffix.push_back(string(1, src[i]));

        int count = GetSameCount(prefix, suffix);
        table[i] = count;
    }

    return table;
}

实现2-向后移动位数： 已匹配的字符数 - 对应的部分匹配值

已知空格与D不匹配时，前面六个字符"ABCDAB"是匹配的。查表可知，最后一个匹配字符B对应的"部分匹配值"为2，因此按照下面的公式算出向后移动的位数：移动位数 = 已匹配的字符数 - 对应的部分匹配值
因为 6 - 2 等于4，所以将搜索词向后移动4位。

// dest中是否包含src
void kmp(const string& src, const string& dest)
{
    vector<int> table = MatchTable(src);

    int i = 0;
    while (i < dest.size()) { 
        int j = 0;
        int tmpi = i;
        // 比较
        for (; j < src.size() && i < dest.size(); tmpi++, j++) {
            if (dest[tmpi] != src[j]) {
                break;
            }
        }
        if (j == src.size()) {
            // 找到一个匹配的子字符串
            cout << "find a substr in " << dest << " at " << i << endl;
            i = tmpi;
            continue;
        }
        if (j == 0) {
            i++;
            continue;
        }
        int acount = j; // 已匹配的个数
        int offset = acount - table[j - 1];  // 移动位数 = 已匹配的字符数 - 对应的部分匹配值
        if (offset <= 0) {
            i++;
        }
        else {
            i += offset;
        }
    }
}