串的模式匹配
现考虑一个常用操作，在字符串s(我们称为主串）中的第pos开始处往后查找，看在主串s中有没有和子串p相匹配的的，如果有，则返回字串p第一次出现的位置。
暴力求解
int Index(char s[], char p[], int pos)
{
int i=pos,j=0;
while(s[i] != '\0' && p[j] != '\0') /* 没有到达结尾 */
if(s[i] == p[j]) {
i++; j++; /* 如果相等继续比较后面的字符 */
}
else {
i = i-j+1; /* i回到比较起点的后一个 */
j = 0; /* j从新开始 */
}
if(p[j] == '\0') /* 匹配成功 */
return i-j; /* 返回成功那次的比较起点 */
else
return -1; /* 返回 -1 代表找不到位置 */
}
KMP算法
相比暴力算法多了一个字串的next映射函数，而该算法的核心和技巧就在于next数组上的求解。
int KmpSearch(char* s, char* p)
{
int i = 0;
int j = 0;
int sLen = strlen(s);
int pLen = strlen(p);
while (i < sLen && j < pLen)
{
//①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
if (j == -1 || s[i] == p[j])
{
i++;
j++;
}
else
{
//②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
//next[j]即为j所对应的next值
j = next[j];
}
}
if (j == pLen)
return i - j;
else
return -1;
}
next的求解
void GetNext(char* p,int next[])
{
int pLen = strlen(p);
next[0] = -1;
int k = -1;
int j = 0;
while (j < pLen - 1) {
//p[k]表示前缀，p[j]表示后缀
if (k == -1 || p[j] == p[k]) {
++k;
++j;
next[j] = k;
}
else {
k = next[k];
}
}
}
或者
//优化过后的next 数组求法
void GetNextval(char* p, int next[])
{
int pLen = strlen(p);
next[0] = -1;
int k = -1;
int j = 0;
while (j < pLen - 1)
{
//p[k]表示前缀，p[j]表示后缀
if (k == -1 || p[j] == p[k]) {
++j;
++k;
//较之前next数组求法，改动在下面4行
if (p[j] != p[k])
next[j] = k; //之前只有这一行
else
//因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]
next[j] = next[k];
}
else {
k = next[k];
}
}
}