首页 > 代码库 > M - Substrings
M - Substrings
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.
InputThe 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.
OutputThere 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
#include<iostream> #include<algorithm> #include<cstdio> #include<vector> #include <sstream> #include<string> #include<cstring> #include<list> using namespace std; #define MAXN 102 #define INF 0x3f3f3f3f #define M 10007 typedef long long LL; /* 枚举第一个串的所有子串 找到就停止 */ char s[MAXN][MAXN]; int Next[MAXN]; void kmp_pre(char t[]) { int m = strlen(t); int j,k; j = 0;k = Next[0] = -1; while(j<m) { if(k==-1||t[j]==t[k]) Next[++j] = ++k; else k = Next[k]; } } bool KMP(char t[],char s[]) { kmp_pre(t); int n = strlen(s),m=strlen(t); int i,j; j = 0; for(i=0;i<n;i++) { while(j>0&&s[i]!=t[j]) j = Next[j]; if(s[i]==t[j]) j++; if(j>=m) return true; } return false; } int main() { int T,n; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=0;i<n;i++) scanf("%s",s[i]); int len = strlen(s[0]); bool f = false; for(int l=len;l>0;l--) { for(int i=0;i+l<=len;i++) { char t1[MAXN] = {0},t2[MAXN] = {0}; strncpy(t1,s[0]+i,l); for(int j=0;j<l;j++) t2[j] = t1[l-1-j]; int j; //cout<<t1<<endl<<t2<<endl; for(j=1;j<n;j++) { if(KMP(t1,s[j]) ||KMP(t2,s[j])) continue; else break; } if(j==n) { f = true; printf("%d\n",l); i = INF; l = -1; } } } if(!f) printf("0\n"); } }
M - Substrings
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。