kmp字符串匹配

KMP字符串匹配

找出模式串里后缀和前缀相同的地方。比如test = “aabaabaac” , pattern = “aabaac”， 进行匹配的时候在pattern的最后的字符c处无法匹配，则看pattern的后缀aa和前面test的下标0处的aa相同，可以再针对下标2处的b进行继续匹配。

next数组存的就是当test和pattern匹配不上的时候应该从新从pattern的哪开始重新匹配，图中是next数组计算的过程。next数组的具体过程见图（备注：图红色的字应该是指针不后移）：

下图是在俩字符串进行匹配过程中，next数组的使用方法：

算法，返回的ans是匹配上了在text的起始位置：

int kmp_strStr(string &test, string &pattern){
    int next[1000] = {0};
    for (int i = 1,j = 0; i <pattern.size();) {
        if (pattern[i] == pattern[j]) {
            next[i] = j + 1;
            i++;
            j++;
        } else {
            //go back
            if (j == 0) {
                next[i] = 0;
                i++;
            } else {
                j = next[j-1];
            }
        }
    }
    //the location of match
    int ans = -1;
    for (int i = 0, j = 0; i < test.size(); ) {
        if (test[i] == pattern[j]){
            i++;
            j++;
            // pattern reachs the end, all matched
            if (j == pattern.size()) {
                ans = i - j;
                break;
            }
        } else {
            if (j == 0){
                i++;
            } else {
                //j go back
                j = next[j - 1];
            }
        }
    }
    return ans;
}

void test_kmp_strStr(){
    string test, pattern;
    cin >> test >> pattern;
    cout << kmp_strStr(test,pattern) << endl;
}

Sunday算法

如果pattern和text没有匹配上，看test对应pattern的下一个字符，这个字符应该会参与到下一轮的字符比较中，因此可以根据这个字符对pattern进行移动匹配。见图：

算法参考实现，注意每一轮匹配之后pattern的指针需要重置为0：

// sunday: string match algorithm
int sunday_strStr(string &text, string &pattern) {
    // 对应的字符最后一次出现在pattern中的位置
    int num[128];
    for (int i = 0; i < 128; i++) {
        // init the length, the char never show in pattern
        num[i] = pattern.size() + 1;
    }
    for (int i = 0; i < pattern.size(); i++){
        num[pattern[i]] = pattern.size() - i;
    }
    int ans = -1;
    //i起始位置 + pattern的长度 <= 文本长度，就一直匹配；一轮匹配之后pattern的指针重置为0
    for (int i = 0, j = 0; i + pattern.size() <= text.size(); j = 0) {
        while (j < pattern.size() && pattern[j] == text[i+j]) {
            j++;
        }
        // match success
        if (j == pattern.size()) {
            //i do not move
            ans = i;
            break;
        }
        // match failed, then i = i + num[?]
        i += num[text[i + pattern.size()]];
    }
    return ans;
}