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\le n\le 50000,1\le n\le 100000,0\le x_i,y_i\le n?1$

solution

非常原始的暴力：每一次都對$y$建后綴自動機，然后將$x$放上去匹配
肯定$T$，GG不用說

優化1： 每一次都重新建后綴自動機，著實太奢侈了
考慮將$y$排個序，相同的$y$就只建立一個后綴自動機，循環使用即可

優化2： 要知道后綴自動機匹配的時間就是$x$的長度
那么為了優化時間，每次就對長串建立后綴自動機，用短串去跑匹配

優化3： 記憶化！對于相同的$x$，沒有必要做無用功

然后就這么$A$了！！時間復雜度$O(n\sqrt{n})$

---

還有另外一種方法，不過俺沒有寫

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; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【正睿2021寒假省选第二轮集训 day 1】串 （后缀自动机+记忆化）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。