字符匹配算法是字符处理的一种基本操作，大致可分为【常规匹配算法】和【KMP算法】
【常规字符匹配算法】如下：
int index(char* s,char* t,int pos)
{
int i = pos;
int j = 1;
while( i<strlen(s) && j< strlen(t))
{
if( s[i] == t[j] )
{
++i;
++j;
}
else
{
i = i-j+1;
j = 0;
}
}
if( j == strlen(t) )
return i-strlen(t);
else
return -1;
}
这个算法在实际中经常使用，但有许多不必要的比较。算法复杂度为O(m*n)，但实际工作中效率近似O(m+n)，比较坏的情况较少出现。
【KMP算法】如下：
void get_next(char* t,int t_len,int *next)
{
int i = 0;
int j = -1;
next[0] = -1;
while( i<t_len )
{
if( j==-1 || t[i] == t[j] )
{
++i; ++j;
if(i<t_len)
{
if(t[i] != t[j])
next[i] = j;
else
next[i] = next[j];
}
}
else
j = next[j];
}
}
int index_KMP(char* s,char *t, int pos)
{
int s_len = strlen(s);
int t_len = strlen(t);
/*建立next数组记录跳步*/
int *next = new int[t_len];
get_next(t,t_len,next);
/*开始匹配*/
int i = pos;
int j = 0;
while( i<s_len && j<t_len )
{
if( j==-1 || s[i] == t[j] )
{ ++i; ++j; }
else
{ j = next[j];}
}
delete[] next;
/*返回结果*/
if( j == t_len )
return i-t_len;
else
return -1;
};
其中具体的匹配算法和常规算法十分类似，但是多了一个next数据来记录跳步，这样可以减少大量不必要的比较操作。上面的KMP算法采用的是一种改进的KMP算法，避免了KMP算法有时候做多余比较的一些情况（参见严蔚敏《数据结构》）。KMP算法将算法的时间复杂度降到了O(m+n)，但也用到了O(n)的辅助空间，一般来说匹配的模式串都不会太长，所以一般辅助空间都是很小的，所以空间耗费是不需要多担心的。但是new操作建立next数据却是很费时间的，尤其是大量频繁调用KMP匹配算法的时候，这导致KMP可能比常规算法还慢，解决办法是判断模式串长度，一般情况下，都采用堆分配，最终算法如下：
void get_next(char* t,int t_len,int *next)
{
int i = 0;
int j = -1;
next[0] = -1;
while( i<t_len )
{
if( j==-1 || t[i] == t[j] )
{
++i; ++j;
if(i<t_len)
{
if(t[i] != t[j])
next[i] = j;
else
next[i] = next[j];
}
}
else
j = next[j];
}
};
int index_KMP_large(char* s,int s_len,char *t,int t_len, int pos)
{
/*建立next数组记录跳步*/
int *next = new int[t_len];
get_next(t,t_len,next);
/*开始匹配*/
int i = pos;
int j = 0;
while( i<s_len && j<t_len )
{
if( j==-1 || s[i] == t[j] )
{ ++i; ++j; }
else
{ j = next[j];}
}
delete[] next;
/*返回结果*/
if( j == t_len )
return i-t_len;
else
return -1;
};
int index_KMP_fast(char* s,int s_len,char *t,int t_len, int pos)
{
/*建立next数组记录跳步*/
int next[256];
get_next(t,t_len,next);
/*开始匹配*/
int i = pos;
int j = 0;
while( i<s_len && j<t_len )
{
if( j==-1 || s[i] == t[j] )
{ ++i; ++j; }
else
{ j = next[j];}
}
/*返回结果*/
if( j == t_len )
return i-t_len;
else
return -1;
};
int index_tmp(char *s, char *t, int pos)
{
int s_len = strlen(s);
int t_len = strlen(t);
int index = -1;
if(t_len > s_len)
return index;
if(t_len < 256 )
index = index_KMP_fast(s,s_len,t,t_len,pos);
else
index = index_KMP_large(s,s_len,t,t_len,pos);
return index;
};
上述的写法，使得整个算法看山去，特别长而繁琐。你可以把代码写得更加简洁：
void get_next(char* t,int t_len,int *next)
{
int i = 0;
int j = -1;
next[0] = -1;
while( i<t_len )
{
if( j==-1 || t[i] == t[j] )
{
++i; ++j;
if(i<t_len)
{
if(t[i] != t[j])
next[i] = j;
else
next[i] = next[j];
}
}
else
j = next[j];
}
}
int index_op(char *s, char *t, int pos)
{
int s_len = strlen(s);
int t_len = strlen(t);
int flag = 0;
if( t_len > s_len )
return -1;
int *next = NULL;
if( t_len <256 )
{
int tmp[256];
next = tmp;
}
else
{
next = new int[t_len];
flag = 1;
}
get_next(t,t_len,next);
/*开始匹配*/
int i = pos;
int j = 0;
while( i<s_len && j<t_len )
{
if( j==-1 || s[i] == t[j] )
{ ++i; ++j; }
else
{ j = next[j];}
}
if( flag==1 )
delete []next;
/*返回结果*/
if( j == t_len )
return i-t_len;
else
return -1;
};
另外，最后提一句，要理解KMP算法，按照一般课本的方式显得特别繁琐，容易绕晕，其实KMP算法的本质就是模拟DFA(有限状态自动机)，从自动机的角度理解KMP其实才是最简洁直观的。