题目描述给定两个由字母a、t、c、g组成的字符串分别代表DNA\texttt{DNA}DNA的两条链长度不超过300300300。要求找出它们的所有最长公共子串连续的字符序列并按字典序升序输出。若不存在任何公共子串则输出No common sequence.。每个测试用例输出后跟一个空行。输入格式输入包含多个测试用例两个连续测试用例之间有一个空行。每个测试用例包含两行每行一个字符串。输出格式对于每个测试用例输出所有最长公共子串每行一个按字典序升序排列。若不存在公共子串则输出No common sequence.。每个测试用例输出后跟一个空行。样例输入atgc tga atgc gctg样例输出tg gc tg题目分析求两个字符串的最长公共子串连续是所有公共子串中长度最大的那些。由于字符串长度仅有300300300可以采用枚举所有子串并检查的方法复杂度O(n3)O(n^3)O(n3)在n300n300n300时约为2.7×1072.7 \times 10^72.7×107在时限内完全可行。也可使用后缀数组Suffix Array\texttt{Suffix Array}Suffix Array或后缀自动机SAM\texttt{SAM}SAM在O(nlog⁡n)O(n \log n)O(nlogn)内求解但实现稍复杂。本题提供了一种利用后缀数组的解法能够高效求出所有最长公共子串。解题思路采用后缀数组结合高度数组height\texttt{height}height的经典方法。将两个字符串拼接为一个长串中间插入一个分隔符其数值小于任何字母的ASCII\texttt{ASCII}ASCII码。然后构建该长串的后缀数组和高度数组。高度数组height[i]\textit{height}[i]height[i]表示后缀数组中第iii个后缀与第i−1i-1i−1个后缀的最长公共前缀长度。若两个后缀分别来自两个不同的原字符串则它们的最长公共前缀即为原字符串的一个公共子串。遍历高度数组当height[i]\textit{height}[i]height[i]大于当前记录的最长长度并且相邻两个后缀分别属于两个不同字符串时则更新最长长度并清空结果集将对应的子串加入结果集若相等则继续加入。最后按字典序输出结果。由于后缀数组本身按字典序排列得到的子串自然有序。具体实现中需注意分隔符的位置以及如何判断后缀属于哪个字符串。若分隔符的位置为sepsepsep则后缀起始位置小于sepsepsep属于第一个字符串大于sepsepsep属于第二个。在遍历高度数组时检查相邻两个后缀的归属关系避免来自同一字符串的重复计数。最终得到所有最长公共子串。代码实现// DNA Sequencing// UVa ID: 760// Verdict: Accepted// Submission Date: 2018-05-21// UVa Run Time: 0.000s//// 版权所有C2018邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXN610;voidradixSort(int*s,int*a,int*b,intn,intm){staticintcnt[MAXN];memset(cnt,0,sizeof(cnt));for(inti0;in;i)cnt[s[a[i]]];for(inti1;im;i)cnt[i]cnt[i-1];for(intin-1;i0;i--)b[--cnt[s[a[i]]]]a[i];}voidsuffixArray(int*s,int*sa,intn,intm){staticintranks[MAXN]{},a[MAXN]{},b[MAXN]{};iota(ranks,ranksMAXN,0);radixSort(s,ranks,sa,n,m);ranks[sa[0]]0;for(inti1;in;i){ranks[sa[i]]ranks[sa[i-1]];ranks[sa[i]](s[sa[i]]!s[sa[i-1]]);}for(inti0;(1i)n;i){for(intj0;jn;j){a[j]ranks[j]1;b[j](j(1i)n)?0:(ranks[j(1i)]1);sa[j]j;}radixSort(b,sa,ranks,n,n);radixSort(a,ranks,sa,n,n);ranks[sa[0]]0;for(intj1;jn;j){ranks[sa[j]]ranks[sa[j-1]];ranks[sa[j]](a[sa[j-1]]!a[sa[j]]||b[sa[j-1]]!b[sa[j]]);}}}voidgetHeight(int*s,int*sa,int*height,intn){staticintranks[MAXN]{};height[0]0;for(inti0;in;i)ranks[sa[i]]i;for(inti0,k0;in;i,(k?k--:0)){if(ranks[i])while(s[ik]s[sa[ranks[i]-1]k])k;height[ranks[i]]k;}}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases0;ints[MAXN]{},sa[MAXN]{},height[MAXN]{};string s1,s2;while(cins1s2){if(cases0)cout\n;setstringcommon;memset(s,0,sizeof(s));memset(height,0,sizeof(height));memset(sa,0,sizeof(sa));intn0,m128,separator0,longest1;for(inti0;is1.length();i)s[n]s1[i];separatorn,s[n]1;for(inti0;is2.length();i)s[n]s2[i];suffixArray(s,sa,n,m);getHeight(s,sa,height,n);for(inti1;in;i)if(height[i]longest){if((separatorsa[i-1]separatorsa[i])||(separatorsa[i-1]separatorsa[i])){if(height[i]longest)common.clear();longestheight[i];if(separatorsa[i])common.insert(s1.substr(sa[i],longest));elsecommon.insert(s1.substr(sa[i-1],longest));}}if(common.size()0){for(autosubstring:common)coutsubstring\n;}elsecoutNo common sequence.\n;}return0;}总结本题通过后缀数组和高度数组高效求解两个字符串的最长公共子串。由于后缀数组本身有序可自然获得字典序升序的结果。注意在比较相邻后缀时需判断它们是否来自不同字符串以避免同一字符串内的重复。该解法时间复杂度O(nlog⁡n)O(n \log n)O(nlogn)空间O(n)O(n)O(n)适用于长度为300300300的字符串但实际上可扩展到更大规模。若使用简单的枚举法代码更易理解但后缀数组方法体现了字符串算法的经典思想适合学习与练习。