rockdu
Problem Description
> The Eternal Fleet was built many centuries ago before the time of Valkorion by an unknown race on the planet of Iokath. The fate of the Fleet's builders is unknown but their legacy would live on. Its first known action was in the annihilation of all life in Wild Space. It spread across Wild Space and conquered almost every inhabited world within the region, including Zakuul. They were finally defeated by a mysterious vessel known as the Gravestone, a massive alien warship that countered the Eternal Fleet's might. Outfitted with specialized weapons designed to take out multiple targets at once, the Gravestone destroyed whole sections of the fleet with a single shot. The Eternal Fleet was finally defeated over Zakuul, where it was deactivated and hidden away. The Gravestone landed in the swamps of Zakuul, where the crew scuttled it and hid it away.
>
> — Wookieepedia
The major defeat of the Eternal Fleet is the connected defensive network. Though being effective in defensing a large fleet, it finally led to a chain-reaction and was destroyed by the Gravestone. Therefore, when the next generation of Eternal Fleet is built, you are asked to check the risk of the chain reaction.
The battleships of the Eternal Fleet are placed on a 2D plane of n rows. Each row is an array of battleships. The type of a battleship is denoted by an English lowercase alphabet. In other words, each row can be treated as a string. Below lists a possible configuration of the Eternal Fleet.
aa
bbbaaa
abbaababa
abba
If in the x-th row and the y-th row, there exists a consecutive segment of battleships that looks identical in both rows (i.e., a common substring of the x-th row and y-th row), at the same time the substring is a prefix of any other row (can be the x-th or the y-th row), the Eternal Fleet will have a risk of causing chain reaction.
Given a query (x, y), you should find the longest substring that have a risk of causing chain reaction.
>
> — Wookieepedia
The major defeat of the Eternal Fleet is the connected defensive network. Though being effective in defensing a large fleet, it finally led to a chain-reaction and was destroyed by the Gravestone. Therefore, when the next generation of Eternal Fleet is built, you are asked to check the risk of the chain reaction.
The battleships of the Eternal Fleet are placed on a 2D plane of n rows. Each row is an array of battleships. The type of a battleship is denoted by an English lowercase alphabet. In other words, each row can be treated as a string. Below lists a possible configuration of the Eternal Fleet.
aa
bbbaaa
abbaababa
abba
If in the x-th row and the y-th row, there exists a consecutive segment of battleships that looks identical in both rows (i.e., a common substring of the x-th row and y-th row), at the same time the substring is a prefix of any other row (can be the x-th or the y-th row), the Eternal Fleet will have a risk of causing chain reaction.
Given a query (x, y), you should find the longest substring that have a risk of causing chain reaction.
Input
The first line of the input contains an integer T, denoting the number of test cases.
For each test cases, the first line contains integer n (n≤105).
There are n lines following, each has a string consisting of lower case letters denoting the battleships in the row. The total length of the strings will not exceed 105.
And an integer m (1≤m≤100) is following, representing the number of queries.
For each of the following m lines, there are two integers x,y, denoting the query.
For each test cases, the first line contains integer n (n≤105).
There are n lines following, each has a string consisting of lower case letters denoting the battleships in the row. The total length of the strings will not exceed 105.
And an integer m (1≤m≤100) is following, representing the number of queries.
For each of the following m lines, there are two integers x,y, denoting the query.
Output
You should output the answers for the queries, one integer per line.
Sample Input
1 3 aaa baaa caaa 2 2 3 1 2
Sample Output
3 3
Source
Recommend
大意：
•给定n个字符串a1~an。
•有m次询问，每次给出x,y，问ax和ay的满足[是a1~an中至少一个字符串的前缀]的最长公共子串的长度。
•字符串总长s<=100000，m<=100
因为要是至少一个的前缀，处理前缀想到trie树，还需要支持查询，那么我们可以构造AC自动机。把所有字符串串成一个大字符串，并且标记他们在大字符串中的位置。这样我们把每一次的两个串x, y找到。在自动机上跑一遍，更新能到达的点，取两次都能到达的离根节点最远的点的深度为答案。
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define For(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
const int maxn = 1e5 + 5;
char s[maxn];
int n, pos[maxn], m, x, y, t;
namespace AC {
int trie[maxn][26], len[maxn], fail[maxn], cnt, root;
bool tot[2][maxn];
void init() {
cnt = root = 1;
memset(fail, 0, sizeof(fail));
memset(trie, 0, sizeof(trie));
memset(len, 0, sizeof(len));
}
void insert(char * s) {
int now = root, l = strlen(s), id;
For(i, 0, l - 1) {
id = s[i] - 'a';
if(!trie[now][s[i] - 'a']) {
len[++cnt] = len[now] + 1;
now = trie[now][id] = cnt;
}
else now = trie[now][id];
}
}
void create() {
queue<int > q;
q.push(1);
int now, p;
while(!q.empty()) {
now = q.front(), q.pop();
For(i, 0, 25) {
if(!trie[now][i]) continue;
int v = trie[now][i];
p = fail[now], q.push(v);
while(p && !trie[p][i])
p = fail[p];
if(p) fail[v] = trie[p][i];
else fail[v] = 1;
}
}
}
void work(char * s, int l, int t) {
memset(tot[t], 0, sizeof(tot[t]));
int id, now = root, p;
For(i, 0, l - 1) {
id = s[i] - 'a';
now = trie[now][id], p = now;
while(p) {
tot[t][p] = 1;
p = fail[p];
}
}
}
int GetAns() {
int mx = 0;
For(i, 1, cnt) if(tot[0][i] & tot[1][i])
mx = max(mx, len[i]);
return mx;
}
}
int main() {
scanf("%d", &t);
while(t--) {
memset(s, 0, sizeof(s));
AC::init();
scanf("%d", &n);
For(i, 1, n) {
pos[i] = strlen(s);
scanf("%s", s + strlen(s));
AC::insert(s + pos[i]);
}
AC::create();
pos[n + 1] = strlen(s);
scanf("%d", &m);
For(i, 1, m) {
scanf("%d%d", &x, &y);
AC::work(s + pos[x], pos[x + 1] - pos[x], 0);
AC::work(s + pos[y], pos[y + 1] - pos[y], 1);
printf("%d\n", AC::GetAns());
}
}
return 0;
} 
没有帐号? 立即注册