这里记录下《Introduction To Algorithm》邓俊辉的《数据结构》里字符串匹配的两种方法，一个是朴素字符串匹配，一个是KMP字符串匹配，还有其他两个叫做Rabin-Karp与有限自动机法的就暂时不考虑了，因为KMP算法在时间复杂度上都可以取代二者。（其实是笔者偷个懒，节约时间搞点别的去。）
如下是各个算法的复杂度，其中是模式
的长度，
是模式
的长度。
字符串匹配的定义
定义：一个长度为的文本（text）
和一个长度为
的模式
，要求出模式
在文本
内是否出现，以及出现的话在文本
中的位置初始位置在哪，通过初始位置和已知
的长度那么就能完全确定子串
在文本
中位置了，这个便是子串匹配问题，例子如下：
朴素字符串匹配算法：
对字符串匹配做暴力解法，即每一个中的字符，我都会去计算
在这里是不是对的上，这个相信大家都有数了。时间复杂度
,即文本
中的可能有效位置都算一次
的长度
。
代码如下，在对模式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上不就合理了吗？
这个思想便是利用此前成功比对所提供的信息，在安全的前提下尽可能大跨度地右移模式串。
- 先说几个字符串的函数,定义前缀函数
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)。
即肯定来自集合：
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。右下图可知这点。
- 若
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/
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 << " ";
}
