<div class="blogpost-body" id="cnblogs_post_body">
<h1><span style="font-size:24px;">初学KMP的时候，一直不得要领。后来学习AC自动机的时候，一下子明白了KMP实际上是AC自动机的特殊情况。<br></span></h1>
<h1><span style="font-size:24px;">首先贴三段代码，一组是回溯法，暴力求解，另外两个是KMP串模式匹配</span></h1>
<div>
<pre class="blockcode"><code class="language-cpp">/*
回溯法字符串匹配算法就是用一个循环来找出所有有效位移，
该循环对n-m+1个可能的位移中的每一个index值，检查条件为P[0…m-1]= S[index…index+m-1]
（因为模式串的长度是m，索引范围为0…m-1）。该算法思维比较简单（但也常被一些公司做为面试题），
很容易分析出本算法的时间复杂度为O(pattern_length*target_length)
int search(char const*, int, char const*, int)
查找出模式串patn在主串src中第一次出现的位置
plen为模式串的长度
返回patn在src中出现的位置，当src中并没有patn时，返回-1
*/
int search(char const* src, int slen, char const* patn, int plen)
{
int i = 0, j = 0;
while( i < slen && j < plen )
{
if( src[i] == patn[j] ) //如果相同，则两者++，继续比较
{
++i;
++j;
}
else
{
//否则，指针回溯，重新开始匹配
i = i - j + 1; //退回到最开始时比较的位置
j = 0;
}
}
if( j >= plen )
return i - plen; //如果字符串相同的长度大于模式串的长度，则匹配成功
else
return -1;
}</code></pre>
<div>
<pre class="blockcode"><code class="language-cpp">/*
KMP算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。
其基本思想是：每当匹配过程中出现字符串比较不等时，不需回溯i指针，
而是利用已经得到的“部分匹配”结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。
算法的核心关键在于查找匹配串的码表（确定部分匹配后要滑动距离）
*/
#include <stdio.h>
#include <string.h>
int index_KMP(char *s,char *t,int pos);
void get_next(char *t,int *);
char s[10]="abcacbcba";
char t[4]="bca";
int next[4];
int pos=0;
int main()
{
int n;
get_next(t,next);
n=index_KMP(s,t,pos);
printf("%d",n);
return 0;
}
int index_KMP(char *s,char *t,int pos)
{
int i=pos,j=1;
while (i<=(int)strlen(s)&&j<=(int)strlen(t))
{
if (j==0||s[i]==t[j-1])
{
i++;
j++;
}
else j=next[j];
}
if (j>(int)strlen(t))
return i-strlen(t)+1;
else
return 0;
}
void get_next(char *t,int *next)
{
int i=1,j=0;
next[0]=next[1]=0;
while (i<(int)strlen(t))
{
if (j==0||t[i]==t[j])
{
i++;
j++;
next[i]=j;
}
else j=next[j];
}
}</code></pre>
<pre class="blockcode"><code class="language-cpp">#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
int next[1000]; //记录跳转位置
int kmp_next(char *base)
{
int i,j;
i=0;
j=-1;
next[0]=-1; //记录第一个字符的跳转位置为-1
while(base[i]!='\0')
{
//如果跳转到-1，说明只能从头开始匹配；
//如果当前匹配点和跳转后的匹配点匹配
if(j==-1||(base[i]==base[j]))
{
//查看下一匹配点的情况
i++;
j++;
//如果下一匹配点还是匹配的，则下一跳地址一样
if(base[i]==base[j])
{
next[i]=next[j];
}
//如果一匹配点不匹配，则下一跳地址为当前前缀地址
else
{
next[i]=j;
}
}
else
{
j=next[j];
}
}
}
int kmp(char *b,char *base)
{
int i,j;
i=0;j=0;
//通过跳转数组，进行快速匹配
while(b[i]!='\0'&&base[j]!='\0')
{
if(b[i]==base[j])
{
i++;j++;
}
else
{
j=next[j];
if(j==-1)
{
i++;j++;
}
}
}
if(base[j]=='\0')
{
return i-j;
}
else
return -1;
}
int main()
{
char base[]="abacba";
char b[1000];
kmp_next(base);
for(int i=0;i<strlen(base);i++)
{
printf("%d ",next[i]);
}
printf("\n %s\n",base);
while(scanf("%s",b)!=EOF)
{
printf("%d \n",kmp(b,base));
}
system("pause");
}
</code></pre>
<h2 style="color:rgb(51,51,51);font-family:Arial;line-height: |
|
转播
