【链接】h在这里写链接
【题意】
问你n个串里面有没有一个串,使得其余n-1个串都是他的子串。
【题解】
后缀数组.
答案肯定是那个最长的串。
则,把那个串求一下Sa数组(注意仅仅那个最长的串求)。
然后枚举其余n-1个子串。
看看它们是不是那个最长的串的子串；
(可以用一个类似二分的东西判断它是不是子串。);
(字符串比较,如果比当前后缀小,就往后缀小的地方,否则往大的地方,最后判断是不是子串。)
->利用Sa数组。
时间复杂度为O(n*logn)的样子。
感觉又解锁了新姿势。
(这里可以不用获取Height函数了)
【错的次数】
0
【反思】
主串的长度没那么长的时候,用这种方法的确合适。
hdu 2222那题。主串的长度太长了(1e6);
就显得没那么优秀了。
【代码】
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
const int SN = 2e2;
const int MAX_CHAR = 300;//每个数字的最大值。
int s[N + 10];//如果是数字,就写成int s[N+10]就好,从0开始存
int Sa[N + 10], T1[N + 10], T2[N + 10], C[N + 10], T;
int Height[N + 10], Rank[N + 10], idx[N + 10], in[N + 10], tag, L[N + 10], R[N + 10];
int Le[N + 10];
vector <string> vec;
bool flag[N + 10];
void build_Sa(int n, int m) {
int i, *x = T1, *y = T2;
for (i = 0; i<m; i++) C[i] = 0;
for (i = 0; i<n; i++) C[x[i] = s[i]]++;
for (i = 1; i<m; i++) C[i] += C[i - 1];
for (i = n - 1; i >= 0; i--) Sa[--C[x[i]]] = i;
for (int k = 1; k <= n; k <<= 1)
{
int p = 0;
for (i = n - k; i<n; i++) y[p++] = i;
for (i = 0; i<n; i++) if (Sa[i] >= k) y[p++] = Sa[i] - k;
for (i = 0; i<m; i++) C[i] = 0;
for (i = 0; i<n; i++) C[x[y[i]]]++;
for (i = 1; i<m; i++) C[i] += C[i - 1];
for (i = n - 1; i >= 0; i--) Sa[--C[x[y[i]]]] = y[i];
swap(x, y);
p = 1; x[Sa[0]] = 0;
for (i = 1; i<n; i++)
x[Sa[i]] = y[Sa[i - 1]] == y[Sa[i]] && y[Sa[i - 1] + k] == y[Sa[i] + k] ? p - 1 : p++;
if (p >= n) break;
m = p;
}
}
bool contain(string &S, string T) {//最长的那个串和 短串
int l = 1, r = S.size(),temp = -1;
while (l <= r) {
int m = (l + r) >> 1;
if (S.compare(Sa[m], T.length(), T) <= 0)//如果后缀比S来的小。
{
temp = m;
l = m + 1;//可以再大一点
}
else
{
r = m - 1;
}
}
if (temp == -1)
return 0;
else
return S.compare(Sa[temp], T.length(), T) == 0;
}
int main() {
//freopen("F:\rush.txt", "r", stdin);
ios::sync_with_stdio(0), cin.tie(0);
int TT;
cin >> TT;
while (TT--) {
int T;
cin >> T;
int n = 0, ma = 0, idxma;
string ss;
vec.clear();
vec.push_back(" ");
for (int i = 1; i <= T; i++) {
cin >> ss;
vec.push_back(ss);
if ((int)ss.size() > ma) {
ma = (int)ss.size();
idxma = i;
}
}
for (int i = 0; i <= (int) vec[idxma].size() - 1; i++)
s[n++] = vec[idxma][i];
s[n] = 0;
build_Sa(n + 1, MAX_CHAR);//注意调用n+1
bool ok = true;
for (int i = 1; i <= T; i++)
if (idxma!=i){//不能是最大的那个,那个是要被匹配的。
if (!contain(vec[idxma], vec[i])) {
ok = false;
break;
}
}
if (ok) {
cout << vec[idxma] << endl;
}
else
cout << "No" << endl;
}
return 0;
}