2744:子串
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
- 现在有一些由英文字符组成的大小写敏感的字符串，你的任务是找到一个最长的字符串x，使得对于已经给出的字符串中的任意一个y，x或者是y的子串，或者x中的字符反序之后得到的新字符串是y的子串。
- 输入
- 输入的第一行是一个整数t (1 <= t <= 10)，t表示测试数据的数目。对于每一组测试数据，第一行是一个整数n (1 <= n <= 100)，表示已经给出n个字符串。接下来n行，每行给出一个长度在1和100之间的字符串。
- 输出
- 对于每一组测试数据，输出一行，给出题目中要求的字符串x的长度。
- 样例输入
-
2 3 ABCD BCDFF BRCD 2 rose orchid
- 样例输出
-
2 2
要抓住题目中的主要矛盾，最终的答案是所有输入字符串的公共最长字串，所以解题思路就是找到输入字符串中最短的那一个，从长到短，依次遍历他的所有子串，判断是不是其他字符串的子串，如果找到，直接跳出，如果还不行，缩短目标字符串的长度，继续找。两个循环特别关键，一个从大到控制待找字符串的长度，另外一个控制寻找的起点，达到不重不漏的目的。
#include <stdio.h> #include <string.h> using namespace std; void strrevv(char *str) { int l=strlen(str),i,j; char *rev=new char[l+1]; for(i=0,j=l-1;i<l;i++,j--){ rev[i]=str[j]; } rev[i]=' '; strcpy(str,rev); delete []rev; } int main() { int t,n,i,j,k,p,minlen,flag; char a[100][101],str[101],revs[101],min[101]; scanf("%d",&t); while(t--){ scanf("%d",&n); minlen=110; for(i=0;i<n;i++){ scanf("%s",a[i]); int l=strlen(a[i]); if(l<minlen){ minlen=l; strcpy(min,a[i]); } } for(j=minlen;j>=1;j--){ for(k=1;k<=minlen-j+1;k++){ strncpy(str,min+k-1,j); str[j]=' '; strcpy(revs,str); strrevv(revs); flag=0; for(p=0;p<n;p++){ if(strstr(a[p],str)==NULL&&strstr(a[p],revs)==NULL) break; } if(p<n) continue; else{ flag=1; break; } } if(flag==1) break; } printf("%d ",j); } return 0; }