一、字符串中删除子串
【问题描述】编写一个程序，当在一个字符串中出现子串时就删除它（字符串的字符个数不超过1000）。
【输入形式】第一行输入一个字符串，第二行输入一个子串。
【输出形式】程序在下一行输出删除其中所有子串后的字符串。如果字符串不包含子串则输出原字符串本身。
【样例输入1】
I am a boy!
a
【样例输出1】
I m boy!
【样例输入2】
Ah Love!could you and I with Fate conspire
ould
【样例输出2】
Ah Love!c you and I with Fate conspire
【样例说明】
删除第一个字符串中所有的子串，包括连续出现的子串。
#include<stdio.h> #include<malloc.h> #include<string.h> #define SIZE 128 #define INCREAM 10 typedef struct String{ char *data; int len; int size; }String,*PString; int Init_String(PString S){ //初始化 S->data=(char *)malloc(sizeof(char)*SIZE); S->len=0; S->size=SIZE; return 1; } int Creat_String(PString S,char *s){ //串的赋值 int i=0; int n=strlen(s); while(*s!='\0'){ if(S->size<n){ S->data=(char*)realloc(S->data,(S->size+INCREAM)*sizeof(char)); S->size+=INCREAM; } S->data[i++]=*s++; S->len++; } return 1; } int Index_BF(PString S1,PString S2,int start){ //BF算法 int i=start-1,j=0; while(i<S1->len&&j<S2->len){ if(S1->data[i]==S2->data[j]){ i++; j++; }else{ i=i-j+1; j=0; } } if(j>=S2->len){ return i-S2->len+1; }else{ return 0; } } int Print_String(PString S){ int i; for(i=0;i<S->len;i++){ printf("%c",S->data[i]); } printf("\n"); return 1; } int Delete_String(PString S,PString T){ //删除操作 int i,j,k,t; for(i=0;i<S->len;i++){ if(Index_BF(S,T,1)) //找到要删除子串在主串的位置 { t=Index_BF(S,T,1); for(j=0;j<T->len;j++){ //删除次数为子串的长度 for(k=t-1;k<S->len-1;k++){ S->data[k]=S->data[k+1]; } S->len--; //每次删除一个字符后，串的长度减 1 } } } return 1; } int main(){ char s1[100],s2[100]; int next[100]; String S1,S2; Init_String(&S1); Init_String(&S2); gets(s1); gets(s2); Creat_String(&S1,s1); Creat_String(&S2,s2); Delete_String(&S1,&S2); Print_String(&S1); return 0; }
二、BF 算法
【问题描述】
串的模式匹配算法BF的应用。
【输入形式】
第一行输入主串s；
第二行输入模式串t；
输入串中均不包含空格字符。
【输出形式】
模式串在主串s中的出现的每一个位置序号。若一次都未匹配到，则输出0。
【样例输入1】
ababcabcacbab
ab
【样例输出1】
1 3 6 12
【样例输入2】
111113455113232342432432
11
【样例输出2】
1 2 3 4 10
【样例输入3】
fasdfdsfsadfdsdsagetgrdgfdgdf
2312
【样例输出3】
0
【评分标准】
采用BF算法。
#include<stdio.h> #include<malloc.h> #include<string.h> #define SIZE 128 #define INCREAM 10 typedef struct String{ char *data; int len; int size; }String,*PString; int Init_String(PString S){ S->data=(char *)malloc(sizeof(char)*SIZE); S->len=0; S->size=SIZE; return 1; } int Creat_String(PString S,char *s){ int i=0; int n=strlen(s); while(*s!='\0'){ if(S->size<n){ S->data=(char*)realloc(S->data,(S->size+INCREAM)*sizeof(char)); S->size+=INCREAM; } S->data[i++]=*s++; S->len++; } return 1; } int Index_BF(PString S1,PString S2,int start){ //BF算法 int i=start-1,j=0; while(i<S1->len&&j<S2->len){ if(S1->data[i]==S2->data[j]){ i++; j++; }else{ i=i-j+1; j=0; } } if(j>=S2->len){ return i-S2->len+1; }else{ return 0; } } int Prints_String(PString S,PString T){ int x; x=Index_BF(S,T,1); if(x==0) printf("0\n"); while(x!=0){ printf("%d ",x); x=Index_BF(S,T,x+1); //下一次遍历从当前字符后面一个字符开始 } return 1; } int main(){ char s1[100],s2[100]; int next[100]; String S1,S2; Init_String(&S1); Init_String(&S2); gets(s1); gets(s2); Creat_String(&S1,s1); Creat_String(&S2,s2); Prints_String(&S1,&S2); return 0; }
三、KMP 算法
【问题描述】
串的模式匹配算法实现（KMP算法）
【输入形式】
第一行输入主串s；
第二行输入模式串t；
第三行输入起始位置pos；
【输出形式】
输出模式串t的next值（以空格分隔）
输出模式匹配结果
【样例输入1】
ababcabcacbab
abcac
1
【样例输出1】
-1 0 0 0 1
6
【评分标准】
采用kmp算法。(next值从-1开始)
#include<stdio.h> #include<malloc.h> #include<string.h> #define SIZE 128 #define INCREAM 10 typedef struct String{ char *data; int len; int size; }String,*PString; int Init_String(PString S){ S->data=(char *)malloc(sizeof(char)*SIZE); S->len=0; S->size=SIZE; return 1; } int Creat_String(PString S,char *s){ int i=0; int n=strlen(s); while(*s!='\0'){ if(S->size<n){ S->data=(char*)realloc(S->data,(S->size+INCREAM)*sizeof(char)); S->size+=INCREAM; } S->data[i++]=*s++; S->len++; } return 1; } int Next_String(PString S,int next[]){ //Next数组 int i=0,j=-1; next[0]=-1; while(i<S->len){ if((j==-1)||(S->data[i]==S->data[j])){ i++; j++; next[i]=j; }else{ j=next[j]; } } for(i=0;i<S->len;i++){ printf("%d ",next[i]); } printf("\n"); return 1; } int Index_KMP(PString S,PString T,int start,int next[]){ //KMP算法 int i=start-1,j=0; while(i<S->len&&j<T->len){ if(j==-1||S->data[i]==T->data[j]){ i++; j++; }else{ j=next[j]; //next数组 } } if(j>=T->len){ printf("%d\n",i-T->len+1); }else{ printf("0\n"); } } int main(){ char s1[100],s2[100]; int next[100]; String S1,S2; Init_String(&S1); Init_String(&S2); gets(s1); gets(s2); Creat_String(&S1,s1); Creat_String(&S2,s2); Next_String(&S2,next); Index_KMP(&S1,&S2,1,next); return 0; }
四、带通配符“？”的模式匹配
【问题描述】
编写一个具有通配符？的模式匹配算法。?可以与任意一个字符匹配。
【输入形式】
输入主串s；
输入子串t；
输入起始位置pos。
【输出形式】
输出匹配结果：子串第一次出现的位置，若未找到，输出0。
【样例输入1】
there are many cats.
?re
1
【样例输出1】
3
【样例输入2】
thsdfiewnjf fsdfdsjewd
f??f
3
【样例输出2】
13
【样例说明】
?为英文状态符号。由于输入串中可能含有空格，请使用gets读入字符串。
【评分标准】
采用kmp或者bf算法均可。
#include<stdio.h> #include<malloc.h> #include<string.h> #define SIZE 128 #define INCREAM 10 typedef struct String{ char *data; int len; int size; }String,*PString; int Init_String(PString S){ S->data=(char *)malloc(sizeof(char)*SIZE); S->len=0; S->size=SIZE; return 1; } int Creat_String(PString S,char *s){ int i=0; int n=strlen(s); while(*s!='\0'){ if(S->size<n){ S->data=(char*)realloc(S->data,(S->size+INCREAM)*sizeof(char)); S->size+=INCREAM; } S->data[i++]=*s++; S->len++; } return 1; } int Index2_BF(PString S1,PString S2,int start){ //BF算法 int i=start-1,j=0; while(i<S1->len&&j<S2->len){ if((S1->data[i]==S2->data[j])||S2->data[j]=='?'){ //在BF算法中加一个条件即可 i++; j++; }else{ i=i-j+1; j=0; } } if(j>=S2->len){ printf("%d ",i-S2->len+1); }else{ printf("0\n"); } } int main(){ char s1[100],s2[100]; int next[100]; String S1,S2; Init_String(&S1); Init_String(&S2); gets(s1); gets(s2); Creat_String(&S1,s1); Creat_String(&S2,s2); int n; scanf("%d",&n); Index2_BF(&S1,&S2,n); return 0; }
