首页 > 代码库 > nyoj_308_Substring_201405091611
nyoj_308_Substring_201405091611
Substring
时间限制:1000 ms | 内存限制:65535 KB
难度:1
- 描述
-
You are given a string input. You are to find the longest substring of input such that the reversal of the substring is also a substring of input. In case of a tie, return the string that occurs earliest in input.
Note well: The substring and its reversal may overlap partially or completely. The entire original string is itself a valid substring . The best we can do is find a one character substring, so we implement the tie-breaker rule of taking the earliest one first.
- 输入
- The first line of input gives a single integer, 1 ≤ N ≤ 10, the number of test cases. Then follow, for each test case, a line containing between 1 and 50 characters, inclusive. Each character of input will be an uppercase letter (‘A‘-‘Z‘).
- 输出
- Output for each test case the longest substring of input such that the reversal of the substring is also a substring of input
- 样例输入
3 ABCABA XYZ XCVCX
- 样例输出
ABA X XCVCX
- 来源
- 第四届河南省程序设计大赛
- 上传者
- 张云聪
-
1 #include <stdio.h> 2 #include <string.h> 3 int map[60][60]; 4 int main() 5 { 6 int T; 7 scanf("%d",&T); 8 while(T--) 9 { 10 int i,j,len,max=0,t; 11 char str1[60],str2[60]; 12 memset(map,0,sizeof(map)); 13 scanf("%s",str1); 14 len = strlen(str1); 15 for(i=0;i<len;i++) 16 str2[i]=str1[len-1-i]; 17 for(i=0;i<len;i++) 18 { 19 for(j=0;j<len;j++) 20 { 21 if(str1[i]==str2[j]) 22 map[i+1][j+1] = map[i][j]+1; 23 if(map[i+1][j+1]>max) 24 { 25 max = map[i+1][j+1]; 26 t = i+1; 27 } 28 } 29 } 30 for(i=t-max;i<t;i++) 31 printf("%c",str1[i]); 32 printf("\n"); 33 } 34 return 0; 35 }
//最长公共子串
//http://i.cnblogs.com/EditPosts.aspx?postid=3582994
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。