char p[]="abc"; char str[]="aabcd"
1 朴素算法
void naive_string_match(char T[],char P[])//模式P(要匹配的字符串)
{
int n = strlen(T);
int m = strlen(P);
int i=0,j=0;
for(i=0;i
{
for(j=0;j {
if(T[i+j]!=P[j]) break;
}
if(j==m&(T[i+m-1]==P[m-1])){printf("T matches P\n");i=i+m-1;}
}
}
2Rabin-Karp算法
//将字符串变成数字的形式
void rabin_karp(char T[],char P[])
{
int n =strlen(T);
int m =strlen(P);
int a=1,i=0,b=1,j=0;
//a=1,b=2,c=3......
for(i=0;i a=a*(P[i]-'a'+1);
b=b*(T[i]-'a'+1);
}
for(i=0;i {
if(a==b){
for(j=0;j {
if(T[i+j]!=P[j]) break;
}
if(j==m&(T[i+m-1]==P[m-1])) printf("T matches P\n");
}
b=b/(T[i]-'a'+1)*(T[i+m]-'a'+1);
}
}
3有限自动机1>状态集合 2>一个起始状态 3>多个终止状态 4>输入的集合 5>转移函数
转移函数
#define LENGTH sizeof(p)-1
char p[] = "abcd";//要匹配的字符串
int count=4;//字符种类，构造自动机用
int Q[LENGTH][4];//状态转移数组
void finite_auto_maching()
{
int i = 0,j=0,k=0,z=0,t=0;
memset(Q,0,sizeof(Q));
for(i=0;i
{
for(j=0;j
{
if(p[i] == ('a'+j))
{
Q[i][j] = i+1;
}else
{
t=0,k=0;
while(t
Q[i][j] = k;
}
}
}
}
4 KMP算法
#include
#include
char p[] = "abcabca";
int count=0;
int t[sizeof(p)-1];//p后缀的最长前缀
void kmp()
{
int i=0,k=0;
memset(t,0,sizeof(t));
for(i=1;i
{
k = t[i-1];
while(p[k]!= p[i]&&k!=0) k=t[k];
if(p[k]== p[i])
t[i] = k+1;
else t[i] = k;
}
}
int main()
{
kmp();
char a[] = "ababcabcaabcabca";
int i=0,k=0;
for(i=0;i
{
while(a[i]!=p[k]&&k!=0) k = t[k-1];
if(p[k] == a[i] ) k = k+1;
if(k==strlen(p)){ count++;k=0;} printf("%d\n",k);
}
printf("P出现次数:%d\n",count);
system("pause");
return 0;
}
阅读(1709) | 评论(2) | 转发(0) |
给主人留下些什么吧！~~
cangt2011-05-09 09:24:03
还有一个kmp和自动机没总结，改天总结下
GFree_Wind2011-05-06 16:53:27
看到数字那个算法时，我还想溢出了咋办？但后面只有在数字相等的情况下再进行比较。不错。不过怎么没有KMP算法呢
