1. 朴素模式匹配算法（又叫 简单模式匹配算法）
- 基本思路：暴力匹配，从第一个字符开始，挨个匹配，如果不符合，则从第二个字符开始，挨个匹配。
int Index(string s, string t)
{
int i = 0, j = 0;
while(i <= length(s) && j <=length(t))
{
if(s[i] == t[j])
{
i++;
j++;
}else
{
i = i - j + 2; //指向s字符串中下一个字符
j = 0;
}
}
//如果此时 j 大于length(t)，则匹配成功，返回 i - length(t)即匹配字符串起始位置
if(j > length(t)) return i - length(t);
else return 0;
}
2. 首尾匹配算法
基本思路：从第一个字符开始，首先匹配字符串的首尾是否相符，如果相符再挨个匹配。不然，从下一个字符开始匹配。
while( i <= length(s) && j <= length(t))
{
if ( s[i] == t[j] && s[i - 1 + length(t)] == t[j - 1 + length(t)] ) //首尾匹配
{
i++;
k = i;
j++;
while(s[i] == t[j]) //匹配首尾之间的的字符
{
i++;
j++;
}
if (j == length(t))
return i - length(t);
}else{
i++;
j = 0;
}
}
return -1;
3. KMP模式匹配算法
基本思路：通过计算next数组，使得当匹配之时遇到不匹配的字符，不用从头开始匹配，而是从模式字符串中重复且已经匹配过的部分开始。
int KMP(string s, string t, int next[])
{
int i = 0 , j = 0;
while(i <= length(s) && j <= length(t))
{
if (j == 0 || s[i] == t[j])
{
i++;
j++;
}else
j = next[j]; //如果不匹配， j 指向模式串中重复部分的下一个字符
}
if (j > t[0])
return i - t[0];
else
return -1;
}
- 计算next的方法：
- next[1] = 0 , next[2] = 1
- 后面解每一位的next[j]值时，令 k = next[j - 1]
- 将 s[j - 1]与s[k] 进行比较
a. 相等，next[j] = k+1;
b. 不等，令 k = next[k]
I. k != 0，重复第三步
II. k == 0, next[j] = 1
