KMP字符串匹配大算法
关于这个KMP算法的整个实现过程呢，这篇blog写得是非常好的:
KMP算法解读
这里主要是扩展一下KMP的应用。
问题1
从src字符串中找到temple字符串的位置，并且返回期位置
解答1: 暴力匹配算法，效率低
/* s为文本字符串，p为模式字符串，从s找p的位置 */
int ViolentMatch(char *s,char*p)
{
int sLen=strlen(s);
int pLen=strlen(p);
int i=0;
int j=0;
while(i < sLen && j < pLen)
{
/* 1.相等则执行这个 */
if(s[i] == p[j])
{
i++;
j++;
}
else
{
/* 2.不相等则将i回溯，j为0 */
i= i-(j-1);
j=0;
}
}
if(j == pLen)
return i - j;
else
return -1;
}解答2:采用KMP算法进行优化
/* 在模式字符串中,寻找next数组 */
void GetNext(char *p,int next[])
{
int pLen = strlen(p);
next[0] = -1;
/* k为next数组存放的值 */
int k = -1;
int j = 0;
while(j < pLen -1)
{
// printf("the j is %d k is %d,next[j] is %d\n",j,k,next[j]);
if(k == -1 || p[j] == p[k])
{
++k;
++j;
if(p[j] != p[k])
next[j] = k;
else
//因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]
//把当前字母前面的字母对应的值赋值给next[j].
next[j] = next[k];
}
else
{
k = next[k];
// printf("the j is %d k is %d,next[j] is %d\n",j,k,next[j]);
}
}
}
/* 假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置
* 如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；
* 如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。
* 换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值（next 数组的求解会在下文的3.3.3节中详细阐述），即移动的实际位数为：j - next[j]，且此值大于等于1。
*
* 很快，你也会意识到next 数组各值的含义：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如如果next [j] = k，代表j 之前的字符串中有最大长度为k 的相同前缀后缀. 此也意味着在某个字符失配时，该字符对应的next 值会告诉你下一步匹配中，模式串应该跳到哪个位置（跳到next [j] 的位置）。如果next [j] 等于0或-1，则跳到模式串的开头字符，若next [j] = k 且 k > 0，代表下次匹配跳到j 之前的某个字符，而不是跳到开头，且具体跳过了k 个字符
* */
/*
* s 为src字符串，p为temple字符串
* 返回匹配位置
*/
int kmpSearch(char *s,char *p,int next[])
{
int sLen=strlen(s);
int pLen=strlen(p);
int i=0;
int j=0;
GetNext(p,next);
while(i < sLen && j < pLen)
{
/* 1.相等则执行这个 */
if(s[i] == p[j]||j == -1)
{
i++;
j++;
}
else
{
/* 2.如果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;
}问题2
有两个字符串，从这两个字符串中找到他们最长的公共子字符串，其中有一个字符并且返回期位置
解答:这问题比较复杂的。加入有字符串1 “s”，字符串2”t”.加入t是比较短的字符串，我们就t来匹配s.首先我们需要寻找出所有t的子字符串。假如t为”abcdesps”,那么先从第一字母开始，a,ab,abc,abcd…..每次在后面增加1.因为KMP的算法其实是匹配从第一个字符开始的字符串匹配算法。再调用一个递归，依次以a,b,c,d,e,s,p,s开头罗列出所有的字符串，每个字符串都要经过一次kmp匹配算法。
/* 寻找两个字符串的最长公共字串 */
int longCommon(char *s,char *t,int *next,int *maxbegin)
{
int sLen = strlen(s); //src len
int tLen = strlen(t); //temp len
int commlen = 0;
int commBegin = 0;
int subIndex =0 ;
int maxlength = 0;
int maxIndex =0;
int i=0;
int j=0;
int temp = 0;
for(subIndex=0;subIndex < tLen;subIndex++)
{
GetNext(t+subIndex,next);
while(i < sLen && j < (tLen - subIndex))
{
if(j == -1 || s[i] == t[j+subIndex])
{
i++;
j++;
if(j > maxlength)
{
maxlength = j;
maxIndex = i-j;
}
}
else
{
j = next[j];
}
}
/* 从所有字串中选取匹配成功长度最大的值以及最大值对应的开始位置 */
if(maxlength > commlen)
{
commlen = maxlength;
commBegin = maxIndex;
}
}
printf("the commom len is %d \n",commlen);
printf("the commBegin is %d \n",commBegin);
printf("the commom string is \n");
*maxbegin = commBegin;
while(temp < commlen)
{
printf("%c",s[commBegin+temp]);
temp++;
}
printf("\n");
return commlen;
}
int getRealLongCM(char *s,char *t,int *next,int *maxBegin)
{
char *myt;
int sLen = strlen(s); //src len
int tLen = strlen(t); //temp len
int i=0;
int j=0;
int maxlen = 0;
int maxlenAll = 0;
int maxbegin2 = 0;
char temp;
if (sLen > tLen)
{
strcpy(myt,t);
printf("the maxBigen is %s\n",myt);
for(i=0;i < tLen;i++)
{
if(i == 0)
{
maxlen = longCommon(s,myt,next,&maxbegin2);
printf("the maxlen in Lonshit is %d\n\n\n",maxlen);
}
else
{
for(j=0;j < (tLen-i);j++)
{
printf("the i is %d,j is %d\n",i,j);
myt[j] = t[i+j];
printf("the the temp is %c\n",temp);
}
maxlen = longCommon(s,myt,next,&maxbegin2);
printf("the maxlen in Lonshit is %d\n\n\n",maxlen);
}
if(maxlen > maxlenAll)
{
maxlenAll = maxlen;
*maxBegin = maxbegin2;
}
}
}
return maxlenAll;
}这个函数写得有点和乱，找个时间用递归再优化，便简洁一点。