字符串匹配算法

字符串匹配算法，又称模式匹配。此算法一般解决的问题是：给定主串\(str\)和字串\(pattern\)，在主串中寻找子串，并返回子串在主串中出现的位置。

暴力算法

简称\(BF(Brute\:Force)\)算法。基本思想：从主串\((str)\)的第一个字符开始和子串\((pattern)\)的第一个字符进行比较，若相等，则继续比较；否则子串退回第一个字符，重新和主串的第二个字符进行比较。反复如此，直到主串完毕。时间复杂度：\(O(nm)\)。

string str, pattern;

void brute_force() {
    int len1 = str.length();
    int len2 = pattern.length();
    int i, j;
    for (i = 0; i < len1 - len2 + 1; i++) {
        for (j = 0; j < len2; j++) {
            if (str[i + j] != pattern[j]) break;
        }
        if (j == len2) cout << i << " ";
    }
}

看个例子，对文本\(str=ababaaababaa\)和模式\(pattern=aaab\)执行暴力算法。

\(abaabaaababaa\\ \underline{aa}ab\\ \:\:\underline{a}aab\\ \:\:\:\:\underline{aaa}b\\ \:\:\:\:\:\:\underline{aa}ab\\ \:\:\:\:\:\:\:\:\underline{a}aab\\ \:\:\:\:\:\:\:\:\:\:\underline{aaab}\)

比较\(str\)和\(pattern\)中对应字符，如\(pattern\)中带下划线的字符，从\(pattern\)和\(str\)对齐位置开始。遇到不匹配的字符之后，\(str\)和\(pattern\)的匹配失败，然后把\(pattern\)向后移动一位，重新开始匹配。注意在实际的操作中并没有真实的移位操作，该操作是通过改变\(pattern\)的下标实现的。