求Ｎ个字符串的最长公共子串，Ｎ＜＝２０，字符串长度不超过２５５。
例如：Ｎ＝３，由键盘依次输入三个字符串为What is local bus ？
Name some local buses. local bus is a high speed I/O bus close to the processer.则最长公共子串为"local bus".
|
#include <stdio.h>
#include <string.h>
#define MAX_N 20 //字符串的最大数目
#define MAX_LEN 256 //字符串的最大长度(含结束符'\0')
int N;//输入的字符串数
char str[MAX_N][MAX_LEN];//保存所有字符串
int Len[MAX_N];//保存字符串的长度
//字符串匹配,成功返回1,失败返回0
int str_match(char *s1, char *s2, int len)
{
while(len > 0)
{
if(*s1 != *s2)
return 0;
s1++;
s2++;
len --;
}
return 1;
}
//main
void main()
{
int i,s,t,l;
printf("请输入字符串的数目N(N<=20):");
scanf("%d",&N);
gets(str[0]);
printf("请输入%d个字符串(每个字符串以回车结束):\n",N);
for(i=0; i<N; i++)
{
gets(str[i]);
Len[i] = strlen(str[i]);
}
for(l=Len[0]; l>0; l--)
{
for(s=0; s+l-1 < Len[0]; s++)
{
int flag1 = 1;
for(i=1; i<N; i++)
{
int flag2 = 0;
for(t=0; t+l-1 < Len[i]; t++)
{
if(str_match(str[0]+s,str[i]+t,l))
{
flag2 = 1;
break;
}
}
//失败
if(!flag2)
{
flag1 = 0;
break;
}
}
//成功
if(flag1)
{
goto L;//跳到输出
}
}
}
//输出最长公共子串
printf("最长公共子串为:");
L: for(i=0; i<l; i++)
{
printf("%c",*(str[0]+s+i));
}
printf("\n");
} |
