kmp算法(算法是转的)+代码

此算法的确很难理解。但是只要你花耐性去理解;应该是可以理解的;!

所以叫做KMP，是因为这个算法是由Knuth、Morris、Pratt三个提出来的，取了这三个人的名字的头一个字母。这时，或许你突然明白了AVL 树为什么叫AVL，或者Bellman-Ford为什么中间是一杠不是一个点。有时一个东西有七八个人研究过，那怎么命名呢？通常这个东西干脆就不用人名字命名了，免得发生争议，比如“3x+1问题”。扯远了。

个人认为KMP是最没有必要讲的东西，因为这个东西网上能找到很多资料。但网上的讲法基本上都涉及到“移动(shift)”、“Next函数”等概念，这非常容易产生误解（至少一年半前我看这些资料学习KMP时就没搞清楚）。在这里，我换一种方法来解释KMP算法。

假如，A="abababaababacb"，B="ababacb"，我们来看看KMP是怎么工作的。我们用两个指针i和j分别表示，A[i-j+ 1..i]与B[1..j]完全相等。也就是说，i是不断增加的，随着i的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前 j个字符（j当然越大越好），现在需要检验A[i+1]和B[j+1]的关系。当A[i+1]=B[j+1]时，i和j各加一；什么时候j=m了，我们就说B是A的子串（B串已经整完了），并且可以根据这时的i值算出匹配的位置。当A[i+1]<>B[j+1]，KMP的策略是调整j的位置（减小j值）使得A[i-j+1..i]与B[1..j]保持匹配且新的B[j+1]恰好与A[i+1]匹配（从而使得i和j能继续增加）。我们看一看当 i=j=5时的情况。

i = 1 2 3 4 5 6 7 8 9 ……

A = a b a b a b a a b a b …

B = a b a b a c b

j =   1 2 3 4 5 6 7

此时，A[6]<>B[6]。这表明，此时j不能等于5了，我们要把j改成比它小的值j'。j'可能是多少呢？仔细想一下，我们发现，j'必须要使得B[1..j]中的头j'个字母和末j'个字母完全相等（这样j变成了j'后才能继续保持i和j的性质）。这个j'当然要越大越好。在这里，B [1..5]="ababa"，头3个字母和末3个字母都是"aba"。而当新的j为3时，A[6]恰好和B[4]相等。于是，i变成了6，而j则变成了 4：

i = 1 2 3 4 5 6 7 8 9 ……

A = a b a b a b a a b a b …

B =      a b a b a c b

j =         1 2 3 4 5 6 7

从上面的这个例子，我们可以看到，新的j可以取多少与i无关，只与B串有关。我们完全可以预处理出这样一个数组P[j]，表示当匹配到B数组的第j个字母而第j+1个字母不能匹配了时，新的j最大是多少。P[j]应该是所有满足B[1..P[j]]=B[j-P[j]+1..j]的最大值。

再后来，A[7]=B[5]，i和j又各增加1。这时，又出现了A[i+1]<>B[j+1]的情况：

i = 1 2 3 4 5 6 7 8 9 ……

A = a b a b a b a a b a b …

B =      a b a b a c b

j =     1 2 3 4 5 6 7

由于P[5]=3，因此新的j=3：

i = 1 2 3 4 5 6 7 8 9 ……

A = a b a b a b a a b a b …

B =         a b a b a c b

j =         1 2 3 4 5 6 7

这时，新的j=3仍然不能满足A[i+1]=B[j+1]，此时我们再次减小j值，将j再次更新为P[3]：

i = 1 2 3 4 5 6 7 8 9 ……

A = a b a b a b a a b a b …

B =             a b a b a c b

j =            1 2 3 4 5 6 7

现在，i还是7，j已经变成1了。而此时A[8]居然仍然不等于B[j+1]。这样，j必须减小到P[1]，即0：

i = 1 2 3 4 5 6 7 8 9 ……

A = a b a b a b a a b a b …

B =               a b a b a c b

j =             0 1 2 3 4 5 6 7

终于，A[8]=B[1]，i变为8，j为1。事实上，有可能j到了0仍然不能满足A[i+1]=B[j+1]（比如A[8]="d"时）。因此，准确的说法是，当j=0了时，我们增加i值但忽略j直到出现A[i]=B[1]为止。

据上，本人的代码:

#include <iostream>

using namespace std;

int next[100];

char A[100],B[100];

int kmp(char *a,char *b)

{

int i,j;

i=j=0;

int la=strlen(a);

int lb=strlen(b);

while(i<la)

{

if(a[i]==b[j])

{

if(j==lb-1)//////////////!

return i-lb+1;////////!

i++;

j++;

}

else if(j>0)

{

j=next[j-1];///////////!!!不相等时,j就移动到前一个字母的NEXT;

}

else

i++;

}

return -1;

}

void get_next(char *p)

{

int plen,i,j;

plen=strlen(p);

i=1;j=0;

next[j]=0;

while(i<plen)

{

if(p[i]==p[j])//开始有周期

{

next[i]=j+1;///!!!

i++;

j++;

}

else if(j>0)//结束该周期

{

j=0; ////////next[j-1];

}

else/////////周期没有开始都置0;

{

next[i]=0;

i++;

}

}

/*for(i=0;i<7;i++)

cout<<next[i]<<endl;*/

}

int main()

{

scanf("%s",A);/////////测试数据abababaababacb;结果为7;

scanf("%s",B);/////////测试数据ababacb;结果为0012300;

get_next(B);

printf("%d/n",kmp(A,B));

return 0;

}

补充下:

getnext部分:

i=             0   1   2   3   4   5   6; i为该串的移动下标;

位置:       1   2   3   4   5   6   7

a   b   a   b   a   c   b

j=            0   0   1   2   3   0   0; j为next坐标;同时也是周期的坐标;(举个例子;next[2]=j=1时,表示该a在1的位置也有一个a)；

next=     0   0   1   2   3   0   0

[0]  [1] [2] [3] [4] [5] [6]



转载声明：


本文转自 http://blog.163.com/wojiaojason@126/blog/static/124098284201022132550944/?fromdm&fromSearch&isFromSearchEngine=yes

=========================================================================


拓扑排序

#include <iostream>

using namespace std;

int n,m,cnt[27],sum[27],map[27][27],pr[27];

char str[5];

int toposoft()

{

int i,j,num,now,s,flag;

now=flag=0;////////////////!!!

memset(pr,0,sizeof(pr));

for(i=1;i<=n;i++)

cnt[i]=sum[i];///////////用CNT记录，免得修改了sum数组的值;

for(i=1;i<=n;i++)

{

num=0;////////!!!!!!!!!!!!!

for(j=1;j<=n;j++)

if(cnt[j]==0)////////查找入度为0的点，记录入度为0的点;

{

num++;

s=j;

}

if(num==0)

return 0;/////////////入度为0的点一个都没有;

if(num>1)//////////当入度为0的点只有一个是，该序列才有顺序;

flag=1;

pr[now++]=s;///入列

cnt[s]=-1;//////////已经入列的点标记;

for(j=1;j<=n;j++)

if(map[s][j]==1)

cnt[j]--;///////////////删除边;

}

if(flag)

return -1;

return 1;

}

int main()

{

while(1)

{

scanf("%d%d",&n,&m);

if(n==0&&m==0)

break;

memset(map,0,sizeof(map));

memset(sum,0,sizeof(sum));

memset(cnt,0,sizeof(cnt));

int sign=0,i;

for(i=1;i<=m;i++)

{

cin>>str;///////////////!!!!

if(sign)

continue;///////////////!!!

int u=str[0]-'A'+1;

int v=str[2]-'A'+1;

map[u][v]=1;

sum[v]++;

int ans=toposoft();

if(ans==0)

{

printf("Inconsistency found after %d relations./n",i);

sign=1;

}

if(ans==1)

{

printf("Sorted sequence determined after %d relations: ",i);

for(int j=0;j<n;j++)

putchar(pr[j]+'A'-1);

printf("./n");

sign=1;

}

}

if(!sign)

printf("Sorted sequence cannot be determined./n");

}

return 0;

}



转载声明：


本文转自 http://blog.163.com/wojiaojason@126/blog/static/1240982842010214105332122/

=========================================================================

原文： 一些算法拾贝