算法简介
模式匹配
给定主串text和模式串pattern，在主串中查找，如果找到了模式串，返回模式串在主串中的起始位置，从1开始计数。
暴力求解求解模式匹配
算法的核心思想是：蛮力法。即使用两个指针i和j，其中i指针用来遍历text，j指针用来遍历pattern。当text[i]==text[j]的时候，继续比较；如果不相等，此时应当回退，i指针退到上次比较的位置，而j指针需要退至pattern起始位置，也就是0。从而展开新一轮比较。
使用C语言描述如下：
#include <string>
#include <cstdio>
int IndexViolent(string s, string p)
{
int i = 0, j = 0;
int count = 0;//记录比较的次数
while (i < s.length() && j < p.length())
{
count++;
if (s[i] == p[j])
{
i++;
j++;
}
else
{
// 注意细节
// j指针回到0重新进行匹配，i指针回到上次匹配位置
// 其中模式串[0,j-1]和主串[i-j,i-1]上面的字符是相匹配的
// 此时i指针应当回退到起始比较位置的后一个字符重新开始匹配
i = i - j+1;
j = 0;
}
}
printf("比较的次数为%d\n", count);
if (i < s.length())
return i - p.length()+1;
return 0;
}
kmp模式匹配推导
暴力求解可以解决问题，但是时间平均时间复杂度达到了O(m*n)，其中m为模式串的长度，n为主串的长度。当主串是长文本时，算法运行时间比较慢。
回到查找，查找里面的核心操作为比较操作，因此为了降低时间复杂度，必须减少比较的次数。
那么如何减少比较的次数，既然暴力求解算法中每次失配的时候，模式串都是移动一位。那么能不能在失配的时候，模式串向后多移动几位？也就是说假设 text[i]!=pattern[j]，下一次直接比较text[i]和pattern[x]，其中x>=0。这种情况下将减少比较次数，同时最重要的是i指针没有回退。现在当务之急就是找到x的值。
已知主串s和模式串p，假设：在s[i]和p[j]时发生失配，此时说明模式串p[0~j-1]和s[j-1,i-1]是相匹配的，接下来下一轮模式串的匹配位置记为next[j]，其语义为当pattern[j]和主串不匹配的时候，下一轮模式串比较的起始位置为next[j]，其中pattern[0,j-1]和text[i-j,i-1]相匹配，且next数组的长度和pattern数组长度相同。next[j]的语义看起来有一定的递归意味，因为当下一轮next[j]位置没有发生匹配时，此时模式串比较的起始位置应当为next[next[j]]，依次类推，最差的情况应该是一直推到0，此时回到pattern起始位置比较。但是还有一种可能，那就是s[i]在和p[0]匹配时就失败，此时应当是s[i+1]和p[0]进行比较。
为了将这种特殊的情况包括在next数组的语义中，可以让next[0]=-1，而按照语义next[1]的值为0。
输入：主串s和模式串p
输出：匹配起始位置
int index(string s,string p){
int m=s.length();
int n=p.length();
int i=0;
int j=0;
while(j<n && i<m){
if(s[i]==p[j] || j==-1){
// 当前匹配继续向后进行
i++;
j++;
}else{
//不匹配的情况，下一轮模式串从next[j]开始比较
j=next[j];
}
// 还有一种情况，主串在模式串第一位比较时
}
if(j==m){
// 匹配成功
retuen i-j+1;
}else{
return -1;
}
}
接下来的问题便在于构建next数组,还是从next数组的语义出发
next[j]的值的含义：当pattern[j]和主串不匹配的时候，下一轮模式串比较的起始位置为next[j]
经过上述分析，知道next[0]的值为-1,next[1]的值为0
当j>1的时候，假设next[j]=x，x的最大值为x-1。则有p[0,x-1]和p[j-x,j-1]，能不能求出next[j+1]的值？
next[j+1]最大值为x+1，此时p[0,x]和p[j-x,j]相匹配，结合上面的p[0,x-1]和p[j-x,j-1]相匹配，此时有p[x]=p[j]，反过来也成立。
即：若p[x]=p[j]，则有next[j+1]=next[j]+1
但是如果p[x]不等于p[j]呢？此时应当使用循环查看p[j]和p[next[x]]是不是相等，若相等，则next[j+1]=p[next[x]]+1。否则继续向后查看。一直查看到p[0]，还不相等，此时说明next[j+1]的值应当为0
接下来使用代码进行描述
为此需要使用两个变量记录：使用变量i来遍历next数组，确定next[i]的值，【为了生成next数组，至少得遍历一遍数组】使用变量j记录next[i-1]的值。
void generateNext(string p){
next[0]=-1;
int i=0;
int j=-1;
while(i<p.length()){
if(j==-1 || p[i]==p[j]){
// j==-1处理p[i]和p[0]都不匹配得情况
i++;
j++;
next[i]=j;
// 上面三行代码实际上用一行代码更好理解
// next[++i]=++j;
}else{
j=next[j];
}
}
}
kmp模式匹配完整代码
#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
const int MAXLENGTH = 100000;
int nextTable[MAXLENGTH];
/**
* @brief
*
* @param pattern
*/
void generateNext(string pattern)
{
nextTable[0] = -1;
int j = -1; // j 指针当模式失配的时候，此时应当重新进行匹配，如果使用next数组，重新匹配的位置 pattern[0]，又回到起点，而使用 next 数组以后，位置变为 next[j]，next[j]最大为j-1
int i=0;// i 指针用来遍历nextTable数组，是只增不减的
/*
a b a b d
-1 0
*/
while(i<pattern.length()){
// i的值至少始终比j的值大一
// next[j]的值最大为 j-1
// 这也是为什么i初始值为0而j的初始值为-1
if(j==-1 || pattern[i]==pattern[j]){
// 匹配
i++;
j++;
nextTable[i] = j;
}else{
// 失配的时候
// 此时应当找更短的后缀匹配
// j = nextTable[j];
// 代码优化，如果pattern[nextTable[j]]的位置和pattern[j]相等，此时也没有继续比较的必要
do{
j = nextTable[j];
} while (pattern[j] == pattern[nextTable[j]]);
// 循环结束，此时pattern[j] != pattern[nextTable[j]]
// 开启下一轮匹配
}
}
// print next array
for (int i = 0; i < pattern.length();i++){
printf("%d ", nextTable[i]);
}
printf("\n");
}
/**
* @brief kmp模式匹配
*
* @param text
* @param pattern
* @return int
*/
int kmp(string text, string pattern)
{
int n = text.length();
int m = pattern.length();
int i = 0, j = 0;
generateNext(pattern);
while (i < n && j < m)
{
// 匹配的情况，pattern[0]和主串不发生匹配
if (pattern[j] == text[i] || j == -1)
{
i++;
j++;
}
else
{
// 不匹配的情况
j = nextTable[j];
}
}
/*
aba
ba
*/
if(j==m){
return i - j + 1;
}else{
return -1;
}
}
测试代码
// main函数测试多组数据
/*
windows下的运行脚本
cd "d:\01.kaoyan\c_language_learning\" ;
if ($?) { g++ kmp2.cpp -o kmp2 } ;
if ($?) { .\kmp2 } ;
// 更改控制台编码格式为utf8编码
chcp 65001
*/
int main()
{
int caseNumber;
scanf("%d", &caseNumber);
while (caseNumber--)
{
string text, pattern;
cin >> text >> pattern;
printf("模式匹配的位置为%d\n", kmp(text, pattern));
}
return 0;
}