Substrings
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 6238 Accepted Submission(s): 2767
Problem Description
You are given a number of case-sensitive strings of alphabetic characters, find the largest string X, such that either X, or its inverse can be found as a substring of any of the given strings.
Input
The first line of the input file contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case contains a single integer n (1 <= n <= 100), the number of given strings, followed by n lines, each representing one string of minimum length 1 and maximum length 100. There is no extra white space before and after a string.
Output
There should be one line per test case containing the length of the largest string found.
Sample Input
2
3
ABCD
BCDFF
BRCD
2
rose
orchid
Sample Output
2
2
Author
Asia 2002, Tehran (Iran), Preliminary
Recommend
Eddy
1 //寻找最长字串并输出其长度 2 // 思路： 3 // 1、先寻找其中最短字符串str，求子字符串就要先找最短的字符串 4 // 2、根据str搜索满足条件的子字符串 5 // 3、对str的各子字符串从长到短一次判断是否满足条件，直到找到一个符合条件的子字符串为止 6 //strlen：计算字符串长度 7 //strstr：在字符串中寻找子字符串,它的用法用的少，但是碰到了，就要熟练。 8 //strncpy：复制字符串中的字串，它的用法要掌握。 9 //strcpy：复制字符串 10 //怎样找最短字符串，也是值得学习的。。 11 //搜索满足条件的最长子串. 12 #include<stdio.h> 13 #include<string.h> 14 char a[101][101]; 15 int n; 16 void cmp(char *str)//字符串反序 17 { 18 int l,i,g=0; 19 char b[101]; 20 l=strlen(str); 21 for(i=0;i<l;i++) 22 b[g++]=str[l-i-1]; 23 b[g]='\0'; 24 strcpy(str,b); 25 } 26 int search(char *str)//搜索满足条件的最长子串并返回其长度 27 { 28 int l1,l2,i,j,f; 29 char s[101],r[101]; 30 l1=strlen(str);l2=strlen(str); 31 while(l1>0)//搜索不同长度的子串，从最长的子串开始搜索 32 { 33 for(i=0;i<=l2-l1;i++) 34 { 35 strncpy(s,str+i,l1);//strncpy的函数用法必须是str+i不能写成str【i】； 36 strncpy(r,str+i,l1); 37 s[l1]=r[l1]='\0'; 38 cmp(r); 39 f=1; 40 for(j=0;j<n;j++) 41 if(strstr(a[j],s)==NULL && strstr(a[j],r)==NULL) 42 { 43 f=0; 44 break; 45 } 46 if(f==1) 47 return l1; 48 } 49 l1--; 50 } 51 return 0; 52 } 53 54 int main() 55 { 56 int i,minstrlen,substrlen,t;//minstrlen记录最短字符串的长度，substrlen返回最长子串长度 57 char minstr[101]; 58 scanf("%d",&t); 59 while(t--) 60 { 61 scanf("%d",&n); 62 minstrlen=100;//先假设字符串最小长度值为100 63 for(i=0;i<n;i++) 64 { 65 scanf("%s",a[i]); 66 if(strlen(a[i])<minstrlen)//寻找n个字符串中最短的字符串 67 { 68 strcpy(minstr,a[i]); 69 minstrlen=strlen(minstr); 70 } 71 } 72 substrlen=search(minstr); 73 printf("%d\n",substrlen); 74 } 75 return 0; 76 }