一些算法拾贝
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/
=========================================================================
原文： 一些算法拾贝
版权所有: 本文系米扑博客原创、转载、摘录，或修订后发表，最后更新于 2010-06-16 15:42:43
侵权处理: 本个人博客，不盈利，若侵犯了您的作品权，请联系博主删除，莫恶意，索钱财，感谢！
转载注明: 一些算法拾贝 （米扑博客）