输入两个字符串，判断其中一个是否为另一个的子串

算法:

设s1是"主串",s2是可能的"子串"。

这里使用朴素的匹配算法，我们不妨称之为“滑动”比较：

第一轮比较：

可能有第二轮比较：

……

可能有最后一轮比较：

程序1：

#include

#include

int main()

{

int t1,t2,i,j,k,flag=0;

char s1[100],s2[100],s0[100];

printf("Please input two strings:\n");

gets(s1);gets(s2);

t1=strlen(s1);

t2=strlen(s2);

for(i=0;i

{if(flag) break;//此行可以减少循环次数

for(j=i,k=0;s2[k]==s1[j];k++,j++)//A

if(s2[k+1]=='\0') //B

}

if(flag==1)

printf("%s是%s的子串\n",s2,s1);

else

printf("不是子串\n");

return 0;

}

“最好情况”是只进行一轮比较。

“最坏情况”是进行strlen(s1)-strlen(s2)+1轮比较，所以外循环条件是i

程序1略变（A行和B行）：

#include

#include

int main()

{

int t1,t2,i,j,k,flag=0;

char s1[100],s2[100],s0[100];

printf("Please input twos trings:\n");

gets(s1);gets(s2);

t1=strlen(s1);

t2=strlen(s2);

for(i=0;i

}

if(flag==1)

printf("%s是%s的子串\n",s2,s1);

else

printf("不是子串\n");

return 0;

}

程序2：

#include

#include

int main()

{

int t1,t2,i,j,k,flag=0;

char s1[100],s2[100],s0[100];

printf("Please input two strings:\n");

gets(s1);gets(s2);

t1=strlen(s1);

t2=strlen(s2);

for(i=0;i

{

j=0;k=i;

while(s2[j])

if(s1[k]==s2[j])

else

break;

if(j==t2)//或if(s2[j]==0)

}

if(flag==1)

printf("%s是%s的子串\n",s2,s1);

else

printf("不是子串\n");

return 0;

}

用函数的程序举例：

#include

int find(char s[],char t[])

{

int i,j,k,n=-1;

for(i=0;s[i]!='\0';i++)

{

for(j=i,k=0;t[k]==s[j];k++,j++)

if(t[k+1]=='\0')

if(n!=-1) break;

}

return n;

}

int main()

{

char s[]="C program";

char t1[]="gra",t2[]="C";

int pos;

pos=find(s,t1);

if(pos==-1) printf("%s不是%s的子串\n",t1,s);

else printf("%s是%s的子串,起始位置%d（起始下标是%d）\n",t1,s,pos+1,pos);

pos=find(s,t2);

if(pos==-1) printf("%s不是%s的子串\n",t2,s);

else printf("%s是%s的子串,起始位置%d（起始下标是%d）\n",t2,s,pos+1,pos);

return 0;

}

程序3：

#include

#include

int main()

{

int t1,t2,i,j,flag=0;

char s1[100],s2[100],s0[100];

printf("Please input two strings:\n");

gets(s1);gets(s2);

t1=strlen(s1);

t2=strlen(s2);

for(i=0;i

if(flag) break;

j=0;

while(s1[i+j]==s2[j]&&s2[j])

j++;

if(s2[j]==0) //或if(j==t2)

flag=1;

}

if(flag==1)

printf("%s是%s的子串\n",s2,s1);

else

printf("不是子串\n");

return 0;

}

统计子串substr在字符串str中出现的次数：

程序一：

#include

int main()

{

char str[80],substr[40];

int num=0,i,j,k;

printf("请输入字符串:");

gets(str);

printf("请输入子串:");

gets(substr);

for(i=0;str[i]!='\0';i++)

{

for(j=i,k=0;substr[k]==str[j];k++,j++)

if(substr[k+1]=='\0') //substr扫描完了

{ num++;break; }

}

if(num)

printf("子串出现:%d次\n",num);

else

printf("%s不是子串!\n",substr);

return 0;

}

程序二：

#include

#include

int main(){

char str1[100],str2[60];

int i,j,k,s1,s2,num=0;

gets(str1);

gets(str2);

s1=strlen(str1);

s2=strlen(str2);

for(i=0;i

{

j=0;k=i;

while(str2[j])

if(str1[k]==str2[j])

else

break;

if(j==s2)//或if(s2[j]==0)

num++;

}

if(num)

printf("子串出现:%d次\n",num);

else

printf("%s不是子串!\n",str2);

return 0;

}

程序三：

#include

#include

int main(){

char str1[100],str2[60];

int i,j,s1,s2,num=0;

gets(str1);

gets(str2);

s1=strlen(str1);

s2=strlen(str2);

for(i=0;i

j=0;

while(str2[j]==str1[i+j]&&str2[j]!=0)//逐个比较

j++;

if(str2[j]==0)//扫描了完整的str2数组

num++;

}

if(num)

printf("子串出现:%d次\n",num);

else

printf("%s不是子串!\n",str2);

return 0;

}