餐饮网站建设服务器,品牌网站建设 1蝌蚪小,桓台县建设局网站,不会被封的网站谁做description
定义一个字符串的子串是这个字符串的某个连续区间的字符组成的串。比如#xff0c;“djq的子串是d”,“j”,“q”,“dj”,“jq”,和djq。
定义F(a,b)为最长在字符串bb中至少出现一次的字符串a的子串#xff0c;例如#xff1a; F(“d…description
定义一个字符串的子串是这个字符串的某个连续区间的字符组成的串。比如“djq的子串是d”,“j”,“q”,“dj”,“jq”,和djq。
定义F(a,b)为最长在字符串bb中至少出现一次的字符串a的子串例如 F(“dmqdjx”,“jdmqdx”) 4 给定n个字符串s0,s1,…,sn−1和q组询问(xj,yj) 对于每组询问你需要求出F(sxj,syj).
输入格式 第一行两个正整数n,q. 接下来n行每行一个由小写字母组成的字符串表示si. 接下来q行每行两个数xj,yj表示一组询问。
输出格式 输出q行每行一个整数表示答案。
样例 输入样例1
3 3 probieren birkerem sadasment 0 1 1 2 0 2
输出样例1
3 1 2
输入样例2
10 20 aaabbbbbaa babbaaaabb aaaabaabba abbabaaaaa ababaababa aabbbbbbba bbabaaabba baaaababaa abaaaaabab baabbbbabb 1 7 1 8 7 8 7 7 4 4 9 1 5 5 5 8 2 9 8 2 0 7 4 8 5 8 3 0 6 2 2 5 2 2 7 1 5 2 1 1
输出样例2
6 5 7 10 10 4 10 3 5 6 4 5 3 3 5 4 10 6 4 10
数据范围与提示 1≤n≤50000,1≤n≤100000,0≤xi,yi≤n−11\le n\le 50000,1\le n\le 100000,0\le x_i,y_i\le n-11≤n≤50000,1≤n≤100000,0≤xi,yi≤n−1
solution
非常原始的暴力每一次都对yyy建后缀自动机然后将xxx放上去匹配 肯定TTTGG不用说
优化1 每一次都重新建后缀自动机着实太奢侈了 考虑将yyy排个序相同的yyy就只建立一个后缀自动机循环使用即可
优化2 要知道后缀自动机匹配的时间就是xxx的长度 那么为了优化时间每次就对长串建立后缀自动机用短串去跑匹配
优化3 记忆化对于相同的xxx没有必要做无用功
然后就这么AAA了时间复杂度O(nn)O(n\sqrt{n})O(nn) 还有另外一种方法不过俺没有写
code
#include cstdio
#include vector
#include cstring
#include iostream
#include algorithm
using namespace std;
#define maxn 100005
struct SAM {int len, fa;int son[26];
}t[maxn];
struct node {int x, id;node(){}node( int X, int Id ) {x X, id Id;}
};
vector node query[maxn];
vector int G[maxn];
int n, Q, cnt, last;
char s[maxn];
int ans[maxn];void insert( int x ) {int pre last, now last cnt;t[now].len t[pre].len 1;while( pre ! t[pre].son[x] ) t[pre].son[x] now, pre t[pre].fa;if( ! pre ) t[now].fa 1;else {int u t[pre].son[x];if( t[pre].len 1 t[u].len ) t[now].fa u;else {int v cnt;t[v] t[u];t[v].len t[pre].len 1;t[u].fa t[now].fa v;while( pre t[pre].son[x] u ) t[pre].son[x] v, pre t[pre].fa;}}
}bool cmp( node x, node y ) {return x.x y.x;
}int solve( int u ) {int maxx 0, len 0, now 1;for( int i 0;i G[u].size();i ) {int v G[u][i];while( t[now].fa ! t[now].son[v] ) {now t[now].fa;len t[now].len;}if( t[now].son[v] ) {now t[now].son[v];len ;}maxx max( maxx, len );}return maxx;
}int main() {scanf( %d %d, n, Q );for( int i 0;i n;i ) {scanf( %s, s );int len strlen( s );for( int j 0;j len;j )G[i].push_back( s[j] - a );}for( int i 1, u, v;i Q;i ) {scanf( %d %d, u, v );if( G[u].size() G[v].size() ) swap( u, v );query[u].push_back( node( v, i ) );}for( int i 0;i n;i ) {memset( t, 0, sizeof( t ) );cnt last 1;for( int j 0;j G[i].size();j )insert( G[i][j] );sort( query[i].begin(), query[i].end(), cmp );int siz query[i].size();for( int j 0;j siz;j ) {ans[query[i][j].id] solve( query[i][j].x );while( j siz - 1 query[i][j].x query[i][j 1].x ) {ans[query[i][j 1].id] ans[query[i][j].id];j ;}}}for( int i 1;i Q;i )printf( %d\n, ans[i] );return 0;
}
