字符串:求N个字符串的最长公共子串来源: 发布时间:星期三, 2008年11月26日 浏览:26次 评论:0
/**************************************************************************
54. 求N个字符串的最长公共子串,N<=20,字符串长度不超过255。 例如:N=3,由键盘依次输入三个字符串为 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"); } 0
相关文章
读者评论
发表评论 |