Substrings(后缀数组)

描述

传送门:POJ1226

You are given a number of case-sensitive strings of alphabetic characters, find the largest string $X$, such that either $X$, or its inverse can be found as a substring of any of the given strings.

Input

The first line of the input contains a single integer $t$ $(1 ≤ t ≤ 10)$, the number of test cases, followed by the input data for each test case. The first line of each test case contains a single integer $n$ $(1 ≤ n ≤ 100)$, the number of given strings, followed by $n$ lines, each representing one string of minimum length $1$ and maximum length $100$. There is no extra white space before and after a string.

Output

There should be one line per test case containing the length of the largest string found.

Sample Input

1
2
3
4
5
6
7
8
2
3
ABCD
BCDFF
BRCD
2
rose
orchid

Sample Output

1
2
2
2

思路

  • 将每个字符都反过来写一遍,中间用互不相同的且没有在字符串中出现的字符隔开;再把所有的字符串连起来,也用互不相同的且没有出现过的字符隔开,求后缀数组和高度数组。
  • 二分答案,判断是否在每个串或其逆串中出现相同的串。(这类问题很经典,之前的题目中也经常出现,进行分组即可)具体看代码体会~

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

const int maxn = 1 << 18;
int s[maxn];
int sa[maxn], t[maxn], t2[maxn], c[maxn], rnk[maxn], height[maxn];

void build_sa(int m, int n)
{
n++;
int *x = t, *y = t2;
for (int i = 0; i < m; i++) c[i] = 0;
for (int i = 0; i < n; i++) c[x[i] = s[i]]++;
for (int i = 1; i < m; i++) c[i] += c[i - 1];
for (int i = n - 1; ~i; i--) sa[--c[x[i]]] = i;
for (int k = 1; k <= n; k <<= 1)
{
int p = 0;
for (int i = n - k; i < n; i++) y[p++] = i;
for (int i = 0; i < n; i++)
if (sa[i] >= k) y[p++] = sa[i] - k;
for (int i = 0; i < m; i++) c[i] = 0;
for (int i = 0; i < n; i++) c[x[y[i]]]++;
for (int i = 0; i < m; i++) c[i] += c[i - 1];
for (int i = n - 1; ~i; i--) sa[--c[x[y[i]]]] = y[i];
swap(x, y);
p = 1;
x[sa[0]] = 0;
for (int 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;
}
n--;
int k = 0;
for (int i = 0; i <= n; i++) rnk[sa[i]] = i;
for (int i = 0; i < n; i++)
{
if (k) k--;
int j = sa[rnk[i] - 1];
while (s[i + k] == s[j + k]) k++;
height[rnk[i]] = k;
}
}

int N;
int id[maxn];

bool solve(int begin, int end)
{
bool vis[105];
clr(vis, 0);
for (int i = begin; i <= end; i++)
vis[id[sa[i]]] = true;
for (int i = 0; i < N; i++)
if (!vis[i]) return false;
return true;
}

bool ok(int k, int n)
{
int begin = 0, end = 0;
for (int i = 1; i <= n; i++)
{
if (height[i] >= k)
end++;
else
{
if (solve(begin, end)) return true;
begin = end = i;
}
}
if (begin < end && solve(begin, end)) return true;
return false;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int t;
char S[105][105];
scanf("%d", &t);
while (t--)
{
scanf("%d", &N);
for (int i = 0; i < N; i++)
scanf("%s", S[i]);
int n = 0, p = 0, m = 128;
int L = 1, R = 0, ans = 0;
for (int i = 0; i < N; i++)
{
int len = strlen(S[i]);
R = max(len, R);
for (int j = 0; j < len; j++, n++)
id[n] = i, s[n] = S[i][j];
s[n++] = m++;
for (int j = len - 1; ~j; j--, n++)
id[n] = i, s[n] = S[i][j];
s[n++] = m++;
}
s[--n] = 0;
build_sa(m, n);
while (L <= R)
{
int mid = (L + R) >> 1;
if (ok(mid, n))
ans = mid, L = mid + 1;
else
R = mid - 1;
}
printf("%d\n", ans);
}
return 0;
}
捐助作者