其实是一个很经典的字符串问题，但是我们比赛的时候没出。
先看一下UVA11107这题，题意是，找出最长的一个字符串，在至少一半的字符串中出现过。只要把所有的字符串用不同的分隔符分开，然后SA一下，最后二分长度，用height将字符串分组，判断是否超过一半即可。要注意的是，因为分隔符单单用个char已经不够了，所以全部char都换成int，然后用不同的整数来作为分隔符即可。
代码如下：
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
const int N = + ;
typedef long long ll;
const int sep = 'z' + ; /**
* sa[i]:表示排在第i位的后缀的起始下标
* rank[i]:表示后缀suffix(i)排在第几
* height[i]:sa[i-1] 与 sa[i]的LCP(最长公共前缀)值
*
* */
/*
如果整数的话模板改成int.
加一个数a[n] = 0 。 这样他的排名是第一个。
construct(a,n+1); 字符串的话。
len = strlen(str);
construct(s,strlen(s)+1);
排名第0的是个空字符串。 height[i]:sa[i-1] 与 sa[i]的LCP(最长公共前缀)值
所以height[1] = 0;
rank[len] = 0;
sa[0] = len;
*/
int sa[N],rnk[N],height[N];
void construct(const int *s,int n,int m = ) {
static int t1[N],t2[N],c[N];
int *x = t1,*y = t2;
int i,j,k,p,l;
for (i = ; i < m; ++ i) c[i] = ;
for (i = ; i < n; ++ i) c[x[i] = s[i]] ++;
for (i = ; i < m; ++ i) c[i] += c[i - ];
for (i = n - ; i >= ; -- i) sa[--c[x[i]]] = i;
for (k = ; k <= n; k <<= ) {
p = ;
for (i = n - k; i < n; ++ i) y[p++] = i;
for (i = ; i < n; ++ i) if (sa[i] >= k) y[p++] = sa[i] - k;
for (i = ; i < m; ++ i) c[i] = ;
for (i = ; i < n; ++ i) c[x[y[i]]] ++;
for (i = ; i < m; ++ i) c[i] += c[i - ];
for (i = n - ; i >= ; -- i) sa[--c[x[y[i]]]] = y[i];
std::swap(x,y);
p = ; x[sa[]] = ;
for (i = ; i < n; ++ i)
x[sa[i]] = y[sa[i - ]] == y[sa[i]]
&& y[sa[i - ] + k] == y[sa[i] + k] ? p - : p ++;
if (p >= n) break;
m = p;
}
for (i = ; i < n; ++ i) rnk[sa[i]] = i;
for (i = ,l = ; i < n; ++ i) {
if (rnk[i]) {
j = sa[rnk[i] - ];
while (s[i + l] == s[j + l]) l++;
height[rnk[i]] = l;
if (l) l--;
}
}
} char str[];
int s[N];
int End[],len,n;
bool vis[];
vector<int> ans; bool solve(int Len)
{
ans.clear();
int cnt = ;
memset(vis,false,sizeof(vis));
for(int i=;i<=len;i++)
{
if(height[i] >= Len)
{
for(int j=;j<=n;j++)
{
if(sa[i] > End[j-] && sa[i] < End[j]) {cnt += !vis[j]; vis[j] = ;}
if(sa[i-] > End[j-] && sa[i-] < End[j]) {cnt += !vis[j]; vis[j] = ;}
}
}
else
{
if(cnt > n / ) ans.push_back(sa[i-]);
cnt = ;
memset(vis,false,sizeof(vis));
}
}
if(cnt > n / ) ans.push_back(sa[len]);
return ans.size();
} int main()
{
int first = ;
while(scanf("%d",&n) == && n)
{
if(first == ) first = ;
else puts("");
len = ;
for(int i=;i<=n;i++)
{
scanf("%s",str);
for(int j=;str[j];j++) s[len++] = str[j]; s[len++] = sep + i;
End[i] = len-;
}
s[len] = ;
construct(s,len+);
int l = , r = len, Ans = -;
while(l <= r)
{
int mid = l + r >> ;
if(solve(mid)) l = mid + , Ans = mid;
else r = mid - ;
} if(Ans == -) puts("?");
else
{
// 为了得到答案，再solve一遍
solve(Ans);
for(int i=;i<ans.size();i++)
{
for(int j=ans[i],cnt=;cnt<=Ans;j++,cnt++) putchar(s[j]);
puts("");
}
//puts("");
}
}
return ;
}
然后看下F题，题意是，找出最短的一个字符串，只在第一个字符串中出现。那么，一样的套路：全部连接，然后SA一遍，然后分组，找这一组中是不是都只是在第一个字符串中出现（这里采用了一个belong数组来判断每个字符是属于哪个串中的）。
代码如下：
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
const int N = 3e6+;
const int M = 5e4+;
typedef long long ll;
const int sep = 'z' + ; /**
* sa[i]:表示排在第i位的后缀的起始下标
* rank[i]:表示后缀suffix(i)排在第几
* height[i]:sa[i-1] 与 sa[i]的LCP(最长公共前缀)值
*
* */
/*
如果整数的话模板改成int.
加一个数a[n] = 0 。 这样他的排名是第一个。
construct(a,n+1); 字符串的话。
len = strlen(str);
construct(s,strlen(s)+1);
排名第0的是个空字符串。 height[i]:sa[i-1] 与 sa[i]的LCP(最长公共前缀)值
所以height[1] = 0;
rank[len] = 0;
sa[0] = len;
*/
int sa[N],rnk[N],height[N];
void construct(const int *s,int n,int m = ) {
static int t1[N],t2[N],c[N];
int *x = t1,*y = t2;
int i,j,k,p,l;
for (i = ; i < m; ++ i) c[i] = ;
for (i = ; i < n; ++ i) c[x[i] = s[i]] ++;
for (i = ; i < m; ++ i) c[i] += c[i - ];
for (i = n - ; i >= ; -- i) sa[--c[x[i]]] = i;
for (k = ; k <= n; k <<= ) {
p = ;
for (i = n - k; i < n; ++ i) y[p++] = i;
for (i = ; i < n; ++ i) if (sa[i] >= k) y[p++] = sa[i] - k;
for (i = ; i < m; ++ i) c[i] = ;
for (i = ; i < n; ++ i) c[x[y[i]]] ++;
for (i = ; i < m; ++ i) c[i] += c[i - ];
for (i = n - ; i >= ; -- i) sa[--c[x[y[i]]]] = y[i];
std::swap(x,y);
p = ; x[sa[]] = ;
for (i = ; i < n; ++ i)
x[sa[i]] = y[sa[i - ]] == y[sa[i]]
&& y[sa[i - ] + k] == y[sa[i] + k] ? p - : p ++;
if (p >= n) break;
m = p;
}
for (i = ; i < n; ++ i) rnk[sa[i]] = i;
for (i = ,l = ; i < n; ++ i) {
if (rnk[i]) {
j = sa[rnk[i] - ];
while (s[i + l] == s[j + l]) l++;
height[rnk[i]] = l;
if (l) l--;
}
}
} char str[N];
int s[N];
int endlen[N],len,n,belong[N];
char temp[N];
int all;
int from; bool check(int st,int ed,int L)
{
int now = -;
for(int i=st;i<=ed;i++)
{
if(belong[sa[i]] == && endlen[sa[i]] >= L)
{
if(now == -) now = sa[i];
continue;
}
return false;
}
from = now;
return true;
} bool solve(int L)
{
int st = , ed = ;
for(int i=;i<all;i++)
{
if(height[i] >= L) ed++;
else
{
if(check(st,ed,L)) return ;
st = ed = i;
}
}
return check(st,ed,L);
} int main()
{
int T, kase = ;
scanf("%d",&T);
while(T--)
{
printf("Case #%d: ",kase++);
scanf("%d%s",&n,temp);
int now_len = strlen(temp);
len = ;
for(int i=;temp[i];i++)
{
s[len] = temp[i];
belong[len] = ;
endlen[len] = now_len - i;
len ++;
}
s[len] = sep + ; belong[len] = , endlen[len] = ;
int first_len = len ++;
for(int i=;i<=n;i++)
{
scanf("%s",str);
int now_len = strlen(str);
for(int j=;j<now_len;j++)
{
s[len] = str[j];
belong[len] = i;
endlen[len] = now_len - j;
len ++;
}
s[len] = sep + i; belong[len] = i, endlen[len] = ; len++;
}
s[len] = ;
construct(s,len+, + );
all = rnk[first_len];
int l = , r = first_len, ans = -;
while(l <= r)
{
int mid = l + r >> ;
if(solve(mid)) r = mid - , ans = mid;
else l = mid + ;
}
if(ans == -) puts("Impossible");
else
{
for(int i=from;i<from+ans;i++) printf("%c",temp[i]);
puts("");
}
}
return ;
}
感觉二分+SA就是一种套路，可以结合前几天做的那题一起看看，最少出现m次的最长字符串。