字符串匹配算法

#define CHAR_MAX 30

typedef int status;

typedef unsigned char *string;

status substring( string s,int pose ,int len ); void index(string s, string t);

int main() {

int i=0,a,wo; char ch; string s,t,m; string sub;

s=malloc(10000*sizeof(unsigned char)); t=malloc(10000*sizeof(unsigned char)); m=malloc(10000*sizeof(unsigned char)); printf(\"\\n\"); printf(\"\\n\");

printf(\"------------------------------------------------------------------------------- \\n\"); printf(\"几种字符串匹配算法实测：\\n\"); printf(\"\\n\");

printf(\" 按 1 手动输入母字符串S \\n\");

printf(\" 按 2 以TXT格式文章作为母字符串S \\n\"); printf(\" 按其他键退出该程序 \\n\");

scanf(\"%d\

printf(\"\\n\");

printf(\"------------------------------------------------------------------------------- \\n\"); switch(wo) {

case 1: { printf(\"请输入母字符串\\n\");

ch = getchar();

while((ch = getchar()) !='\\n') {s[i]=ch; i++;};

S内容:

s[i]='\\0';

};

break ; case 2:

{

printf(\"\\n\"); printf(\"\\n\");

(End Of File)

printf(\"母字符串S内容为: \\n\"); char chf; FILE* fp; fp = fopen(\"c:\\\\example3.txt\只供读取 if(fp == NULL) //如果失败了 {

printf(\"ERROR！\"); return 1; } int kl=0; //getc()用于在打开文件中获取一个字符

while((chf = getc(fp)) != EOF) //循环获取直至文件结束 EOF标志 {

s[kl]=chf; //打印获取到的字符 kl++; } s[kl]='\\0'; fclose(fp); //关闭文件 printf(\"\\n\"); int as=0; for(;asreturn 0; break; }

// printf(\"字符串长度是：%d\返回值为字符串长

//printf(\"\\n 输出s内容:\\n\");

// for(i=0;iprintf(\"-------------------------------------------------------------------------------\\n\"); printf(\"\\n\");

printf(\"请输入子字符串T内容 : \\n\"); printf(\"\\n\");

i=0;

ch=getchar();

while((ch = getchar()) !='\\n') {t[i]=ch; i++;}; t[i]='\\0';

printf(\"-------------------------------------------------------------------------------\\n\"); /* printf(\"字符串长度是：%d\返回值为字符串长 printf(\"\\n输出t内容:\\n\"); for(i=0;i/* strcpy(t,\"mnkec\");//字符串之间赋值函数； printf(\"\\nt字符串长度是%d\\n\ printf(\"\\n输出t字符串：\\n\"); for(i=0;i/* strcpy( m,strcat(s,t));

// 编译器自带字符串连接函数stracat printf(\"\\n输出m字符串：\\n\"); for(i=0;istrcpy(sub,substring(s,3,2)); //substring函数的验证；

printf(\"\\n输出sub字符串：\\n\");

for(i=0;iprintf(\"\\n字符串长：%d\\n\*/

printf(\"\\n\"); bm(s,t); sundy(s,t); cloudy(s,t); index(s,t);

return 0; }

//上为主函数；

status substring( string s,int pose ,int len )// 子字符串提取函数substring；返回值为子str字符串 {

unsigned char* sub;

sub=malloc(10000*sizeof(unsigned char)); int i=strlen(s); int k=pose+len-1; if(i<0||pose>i||k>i) return NULL;

int a;

for( a=0;astatus bm(string s,string t) {

int m,n;//母子串长度+1 m=strlen(s); n=strlen(t);

int i=n;//检索总长变量n-m int b,bz;//坏字符在母子串位子 int shift=0;//应该移动长度 int suf ;//好字符长度 int k;//计数

unsigned char* sub1;

sub1=malloc(10000*sizeof(unsigned char));

printf(\"\\nBM算法运行得：\");

for(;i<=m; i=i+shift)//判断母串是否检测完 {

int flag=1;//用来辅助跳出嵌套外循环 strcpy(sub1,substring(s,i-n+1,n) ); if(strcmp(sub1,t)==0) {

printf(\"\\n 匹配成功,在母串的第%d 个字符\ shift=1;

}

/* printf(\"\\n输出sub1字符串：\\n\");

for(i=0;iprintf(\"%c\输出sub11字符串 printf(\"\\n\"); */

{//shift函数外围开始

if(strcmp(sub1,t)!=0)

{//shift函数范围开始

if(t[n-1]!=s[i-1])//坏字符算法 {

for(k=0;kif(t[k]==s[i-1])//找到,跳出循环for

{ shift=n-k-1; flag=0; // break; }

if(k==n-1&&t[k]!=s[i-1]) {

shift=n; flag=0; break;

}

// printf(\"坏字符时移动的距离为%d\\n\ }

}

else //好后缀

{ int a=0,g=1;//g为好后缀个数

for(a;a{ if(t[n-a-2]==s[i-a-2]) {++g;} else break; }

// printf(\"\\n输出好后缀字符个数%d\

// 寻找好前缀： // 用来求得shiftg int h;

int shift=-1;//初始值，用来判断后面 string test; string good;

test=malloc(10000*sizeof(unsigned char)); good=malloc(10000*sizeof(unsigned char));

lop:

for(h=1;h<=n-g+1;h++) {

strcpy(good,substring(t,n-g+1,g) ); strcpy(test,substring(t,h,g) ); if(strcmp(good,test)==0)

{ shift=n-g+1-h; break;} }

if(shift<=0) { if(g>1) {--g;

goto lop;} }

if(shift==0)

{//printf(\"\\n输出n%d\\n\ shift=n; }

// printf(\"\\n好后缀时需要移动的距离是%d\

}

}//shift函数范围

}//shift外围函数

}//while函数结束

return 0; }

status sundy(string s,string t)

{

int m,n;//母子串长度+1 m=strlen(s); n=strlen(t);

int i=n;//检索总长变量n-m int b,bz;//坏字符在母子串位子 int shift=0;//应该移动长度 int suf ;//好字符长度 int k;//计数

unsigned char* sub1;

sub1=malloc(2000*sizeof(unsigned char));

printf(\"\\nSUNDY算法运行得：\"); for(;i<=m; i=i+shift)//判断母串是否检测完 {

strcpy(sub1,substring(s,i-n+1,n) ); if(strcmp(sub1,t)==0)

printf(\"\\n 匹配成功,在母串的第%d 个字符\

/* printf(\"\\n输出sub1字符串：\\n\");

for(i=0;iprintf(\"%c\输出sub11字符串 printf(\"\\n\"); */

int flag=1; //用来辅助跳出嵌套外循环

{//shift函数外围开始

if(strcmp(sub1,t)!=0) {//shift函数范围开始

if(t[n-1]!=s[i-1])//坏字符算法 {

for(k=0;kif(t[k]==s[i-1])//找到,跳出循环for

{ shift=n-k-1; flag=0; break; }

if(k==n-1&&t[k]!=s[i-1]) {

shift=n; flag=0; break; }

}

// printf(\"\\n坏字符时移动的距离为%d\\n\ }

}

else shift=1;//匹配成功，后移一位；

}//shift外围函数

}//for函数结束

return 0; }

status cloudy(string s,string t) {

int m,n;//母子串长度+1 m=strlen(s); n=strlen(t);

int i=n;//检索总长变量n-m int b,bz;//坏字符在母子串位子 int shift=0;//应该移动长度 int suf ;//好字符长度 unsigned char* sub1;

sub1=malloc(10000*sizeof(unsigned char));

printf(\"\\nCLOUDY算法运行得：\"); for(;i<=m; i=i+shift)//判断母串是否检测完 {

strcpy(sub1,substring(s,i-n+1,n) ); if(strcmp(sub1,t)==0) {

printf(\"\\n 匹配成功,在母串的第%d 个字符\ shift=1;

}

/* printf(\"\\n输出sub1字符串：\\n\");

for(i=0;iprintf(\"%c\输出sub11字符串 printf(\"\\n\"); */

{//shift函数外围开始

if(strcmp(sub1,t)!=0) {//shift函数范围开始

if(t[n-1]!=s[i-1])//坏字符算法 shift=1;

else //好后缀

{ int a=0,g=1;//g为好后缀个数

for(a;a{ if(t[n-a-2]==s[i-a-2]) {++g;} else break; }

// printf(\"\\n输出好后缀字符个数%d\

// 寻找好前缀： // 用来求得shiftg int h;

int shift=-1;//初始值，用来判断后面 string test; string good;

test=malloc(10000*sizeof(unsigned char)); good=malloc(10000*sizeof(unsigned char));

lop:

for(h=1;h<=n-g+1;h++) {

strcpy(good,substring(t,n-g+1,g) ); strcpy(test,substring(t,h,g) ); if(strcmp(good,test)==0)

{ shift=n-g+1-h; break;} }

if(shift<=0) { if(g>1) {--g;

goto lop;} }

if(shift==0) {

//printf(\"\\n输出n%d\\n\ shift=n; }

// printf(\"\\n好后缀时需要移动的距离是%d\

}

}//shift函数范围

}//shift外围函数

}//while函数结束

return 0; }

void index(string s, string t) {

int m,n,i; string test;

test=malloc(10000*sizeof(unsigned char)); n=strlen(s);m=strlen(t); i=1; int a=0;

int jishu[1000];//数组用来计数匹配成功的位置

printf(\"\\n穷举算法运行得：\\n\"); while(i<=n-m+1){

strcpy(test,substring(s,i,m)); if(strcmp(test,t)!=0) ++i; else {

jishu[a]=i;

printf(\" 匹配成功输出:%d\\n\ ++i;++a;

}// 返回子串在主串中的位置

}//while

//S中不存在与T相等的子串 }//Index