A - DNA Sequencing 后缀数组
题目大意：
给你两个字符串，问两个字符串的最长相同子串，如果有多个则按照字典序输出，如果没有则输出"No common sequence."，输出与输出之间空一行，多组输入。
题解：
这个因为数据范围很小，所以可以不同后缀数组写，不过刚刚学习了这个算法，所以学习了一下后缀数组的写法。
这个题目首先要把两个子串进行合并
-
后缀数组求最长相同子串的长度：因为 (height[i]) 表示的是第 (i) 小的子串和第 (i-1) 小的子串的最长前缀，所以我只需要判断是否存在 (height[i]>0) 并且 (sa[i]) 和 (sa[i-1]) 处于两个不同的子串，取这种 (height[i]) 的最大值即是最长相同子串。
这个可以用二分+哈希的写法来做。
-
然后就是找子串了，我按照 (rk) 来找，如果 (height[i]>=ans) ，那么我就把这个在1还是2的这个位置放入一个 (set) ，如果找不到这样的 (height[i]>=ans) ，那么就判断一下 (set) 里面是不是两个都有，如果是，那么就存下这个开始的位置。
注意一下，要把连续 (rk) 的 (height[i]>=ans) 全部遍历完，这个是为了不重复放值。然后因为 (rk) 是从小到大的放的，所以最后的输出结果也一定是按照字典序的。
这个题目还有一些小小的细节要注意：
- 为了更好的去分割这两个字符串以及为了简化写法，所以要在第一个和第二个的结尾放入不同的非小写字符来区分。
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
char s[maxn];
int height[maxn];
int sa[maxn*2],rk[maxn*2],oldrk[maxn*2],w;
//sa[i] 表示后缀排序第 i 小的编号，rk[i] 表示后缀 i 的排名
// 数组开两倍防止 +w 时的越界
bool cmp(int a,int b){
return rk[a]==rk[b]?rk[a+w]<rk[b+w]:rk[a]<rk[b];
}
int n;
void getSARK(){
for(int i=1;i<=2*n;i++) {
if(i<=n) sa[i] = i,rk[i] = s[i];
else sa[i] = 0,rk[i] = 0;
height[i] = 0;
}
for(w = 1;w<n;w<<=1){
sort(sa+1,sa+1+n,cmp);
for(int j=1;j<=n;j++) oldrk[j] = rk[j];
for(int p=0,i=1;i<=n;i++){
if (oldrk[sa[i]] == oldrk[sa[i - 1]] &&
oldrk[sa[i] + w] == oldrk[sa[i - 1] + w]) {
rk[sa[i]] = p;
} else {
rk[sa[i]] = ++p;
} // 若两个子串相同，它们对应的 rk 也需要相同，所以要去重
}
}
for(int i=1,k=0;i<=n;i++){
if(k) k--;
while(s[i+k]==s[sa[rk[i]-1]+k]) ++k;
height[rk[i]] = k;
}
}
char a[maxn],b[maxn];
int alen,blen,vis[maxn];
set<int>Set;
vector<int>Ans;
int main(){
int cas = 0;
while(~scanf("%s%s",a+1,b+1)){
if(cas) printf("
");
cas++;
alen = strlen(a+1),blen = strlen(b+1),n = alen + blen + 2;
for(int i=1;i<=alen;i++) s[i] = a[i],vis[i] = 1;
s[alen+1] = 'z' + 1,vis[alen+1] = 0;
for(int i=1;i<=blen;i++) s[i+alen+1] = b[i],vis[i+alen+1] = 2;
s[n] = 'a' - 1,vis[n] = 0;
getSARK();
int ans = 0;
for(int i=1;i<=n;i++){
if(vis[sa[i]]+vis[sa[i-1]]==3&&height[i]>ans) {
ans = height[i];
}
}
if(!ans) printf("No common sequence.
");
else {
int fir = 0;
Set.clear(),Ans.clear();
for(int i=1;i<=n+1;i++){
if(height[i]>=ans){
fir = sa[i];
Set.insert(vis[sa[i]]);
Set.insert(vis[sa[i-1]]);
}
else{
if(Set.size()==2) Ans.push_back(fir);
Set.clear();
}
}
for(int i=0;i<Ans.size();i++){
int now = Ans[i];
// printf("i = %d now = %d
",i,now);
for(int j=now;j<=now+ans-1;j++) printf("%c",s[j]);
printf("
");
}
}
}
}