Problem
acm.hdu.edu.cn/showproblem.php?pid=6208
Meaning
有 n 个字符串,问是否能找到其中一串,使得其它串都是它的子串
Analysis
如果存在这个串,那它一定是 n 个中的最长串。所以只要找出最长串,然后看其它串是否都是它的子串。
队友写的 AC自动T,一直超时,后来换成后缀数组过的。
再后来在 AcFun 里听见有 dalao 说 AC自动机 能过,还有用 KMP 和 strstr() 甚至 string 的 find() 过的…(据说不同 AC自动机 模板的常数不同)
Code
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
const int S = 100000, N = S, M = 26;
int sa[S];
inline bool same(int *rnk, int a, int b, int w)
{
return rnk[a] == rnk[b] && rnk[a+w] == rnk[b+w];
}
void da(const char *s, int n, int m)
{
static int rnk[S], tmp[S], cnt[S];
int *x = rnk, *y = tmp;
memset(cnt, 0, sizeof cnt);
for(int i = 0; i < n; ++i)
++cnt[x[i] = s[i] - 'a'];
for(int i = 1; i < m; ++i)
cnt[i] += cnt[i-1];
for(int i = n - 1; i >= 0; --i)
sa[--cnt[x[i]]] = i;
for(int w = 1; w < n; w <<= 1)
{
int num = 0;
for(int i = n - w; i < n; ++i)
y[num++] = i;
for(int i = 0; i < n; ++i)
if(sa[i] >= w)
y[num++] = sa[i] - w;
memset(cnt, 0, sizeof cnt);
for(int i = 0; i < n; ++i)
++cnt[x[i]];
for(int i = 1; i < m; ++i)
cnt[i] += cnt[i-1];
for(int i = n - 1; i >= 0; --i)
sa[--cnt[x[y[i]]]] = y[i];
swap(x, y);
x[sa[0]] = 0;
num = 1;
for(int i = 1; i < n; ++i)
x[sa[i]] = same(y, sa[i-1], sa[i], w) ? num - 1 : num++;
if(num >= n)
break;
m = num;
}
}
string str[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while(T--)
{
int n;
cin >> n;
// 最长串的下标、长度
int id = 0, ml = 0;
for(int i = 0; i < n; ++i)
{
cin >> str[i];
if(ml < str[i].length())
{
id = i;
ml = str[i].length();
}
}
// 构建后缀数组
const char *txt = str[id].c_str();
da(txt, ml, M);
// 查询剩余的串是不是最长串的子串
bool flag = true;
for(int i = 0; i < n; ++i)
if(i != id)
{
bool found = false;
int patlen = str[i].length();
const char *pat = str[i].c_str();
// 二分文本川(最长串)后缀的字典序
// 看模式串式不是文本串的这个后缀的一个前缀
for(int l = 0, r = ml - 1, m, res; l <= r; )
{
m = l + r >> 1;
res = strncmp(pat, txt + sa[m], patlen);
if(!res)
{
found = true;
break;
}
else if(res > 0)
l = m + 1;
else
r = m - 1;
}
// 此串不是最长串的子串
if(!found)
{
flag = false;
break;
}
}
cout << (flag ? txt : "No") << '\n';
}
return 0;
}