题意:给你n个串,每个串都可以选择它的一个长度为n的环形子串(比如abcdf的就有abcdf,bcdfa,cdfab,dfabc,fabcd),求这个n个串的这些子串的最长公共子序列(每个串按顺序提出来字符,而这些字符并不一定要相邻)是什么(输出字典序最小的那个),没有就输出0
题解:看起来很难做,但实际上是10个串,每个串长度为8,也就是对于每个串也只有8个环形n子串,于是我们直接暴力枚举第一串的8种,与第二个串的8个依次求LCS
1 #include<bits/stdc++.h> 2 using namespace std; 3 char a[15][30],pat[30],ans_string[30]; 4 int len[30],ans,n; 5 void solve(int length) 6 { 7 int start,limit,pat_len; 8 int ok=1,flag=0; 9 for (int i=1;i<n;i++) 10 { 11 pat_len=0; 12 flag=0; 13 for (int j=0;j<len[i];j++) 14 if (a[i][j]==pat[0]) 15 { 16 start=j+1; 17 limit=j+len[i]; 18 pat_len=1; 19 while (start<limit && pat_len<length) 20 { 21 if (a[i][start]==pat[pat_len]) pat_len++; 22 start++; 23 } 24 if (pat_len==length) 25 { 26 flag=1; 27 break; 28 } 29 } 30 if (!flag) 31 { 32 ok=0; 33 break; 34 } 35 } 36 if (ok) 37 { 38 if (length > ans || ((ans==length) && (strcmp(pat,ans_string)<0) )) 39 { 40 ans=length; 41 for (int i=0;i<ans;i++) ans_string[i] = pat[i]; 42 ans_string[ans] = ' '; 43 } 44 } 45 } 46 void dfs(int k,int last,int limit) 47 { 48 solve(k); 49 for (int i=last+1;i<limit;i++) 50 { 51 pat[k]=a[0][i]; 52 pat[k+1]=' '; 53 dfs(k+1,i,limit); 54 } 55 return; 56 } 57 int main() 58 { 59 while (scanf("%d",&n)!=EOF) 60 { 61 ans=0; 62 for (int i=0;i<n;i++) 63 { 64 scanf("%s",a[i]); 65 len[i]=strlen(a[i]); 66 } 67 for (int j=0;j<n;j++) 68 { 69 for (int i=0;i<len[j];i++) a[j][i+len[j]]=a[j][i]; 70 a[j][len[j]*2]=' '; 71 } 72 for (int i=0;i<len[0];i++) 73 { 74 pat[0]=a[0][i]; 75 pat[1]=' '; 76 dfs(1,i,i+len[0]); 77 } 78 if (ans>0) printf("%s ", ans_string); else printf("0 "); 79 } 80 }