链接
点击跳转
题解
很暴力的做法就是直接把两个串拼起来，
r
r
r串在前，
l
l
l串在后，中间加一个分隔符，然后跑
k
m
p
kmp
kmp，最后一个位置的
n
e
x
t
next
next值就是答案
如果
r
r
r串的长度小于
∑
l
e
n
g
t
h
\sqrt {\sum length}
∑length
，那么我可以直接把
l
l
l串只保留最后一段长为
l
e
n
g
t
h
r
length_r
lengthr的后缀，然后做
k
m
p
kmp
kmp，单次复杂度是
O
(
∑
l
e
n
g
t
h
)
O(\sqrt {\sum length})
O(∑length
)
但是如果
r
r
r串很长呢
没关系，长度大于
∑
l
e
n
g
t
h
\sqrt {\sum length}
∑length
的串最多有
∑
l
e
n
g
t
h
\sqrt {\sum length}
∑length
个，直接预处理即可。预处理就是把这个很长的串放在前面，其余的串都拼在后面然后跑
k
m
p
kmp
kmp，单次
O
(
∑
l
e
n
g
t
h
)
O(\sum length)
O(∑length)，总复杂度是
O
(
∑
l
e
n
g
t
h
(
∑
l
e
n
g
t
h
)
)
O(\sqrt {\sum length}(\sum length))
O(∑length
(∑length))
令
L
=
∑
l
e
n
g
t
h
L=\sum length
L=∑length
最后的复杂度是
O
(
(
Q
+
L
)
L
)
O((Q+L)\sqrt L)
O((Q+L)L
)
代码
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define iinf 0x3f3f3f3f
#define linf (1ll<<60)
#define eps 1e-8
#define maxn 1000010
#define maxe 1000010
#define cl(x) memset(x,0,sizeof(x))
#define rep(i,a,b) for(i=a;i<=b;i++)
#define drep(i,a,b) for(i=a;i>=b;i--)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
#define de(x) cerr<<#x<<" = "<<x<<endl
using namespace std
;
using namespace __gnu_pbds
;
typedef long long ll
;
typedef pair
<int,int> pii
;
typedef pair
<ll
,ll
> pll
;
ll
read(ll x
=0)
{
ll c
, f(1);
for(c
=getchar();!isdigit(c
);c
=getchar())if(c
=='-')f
=-f
;
for(;isdigit(c
);c
=getchar())x
=x
*10+c
-0x30;
return f
*x
;
}
struct KMP
{
int n
, next
[maxn
], t
[maxn
];
void build(int *r
, int len
)
{
int i
, j
=0;
n
=len
;
for(i
=1;i
<=len
;i
++)t
[i
]=r
[i
]; t
[len
+1]=0;
for(i
=2;i
<=len
;i
++)
{
for(;j
and t
[j
+1]!=t
[i
];j
=next
[j
]);
next
[i
] = t
[j
+1]==t
[i
]?++j
:0;
}
}
int move(int pos
, int x
)
{
for(;pos
and t
[pos
+1]!=x
;pos
=next
[pos
]);
return t
[pos
+1]==x
? pos
+1 : 0;
}
}kmp
;
char s
[maxn
];
int r
[maxn
], start
[maxn
], len
[maxn
], t
[maxn
];
int main()
{
int N
=read(), i
, j
;
rep(i
,1,N
)
{
scanf("%s",s
+1); len
[i
]=strlen(s
+1);
start
[i
] = start
[i
-1]+len
[i
-1]+1;
rep(j
,1,len
[i
])
{
r
[start
[i
]+j
-1] = s
[j
];
}
r
[start
[i
]+len
[i
]]=i
+1000;
}
int L
= start
[N
]+len
[N
], S
= sqrt(L
-N
);
map
<pii
,int> big
;
rep(i
,1,N
)
{
if(len
[i
]<S
)continue;
rep(j
,1,len
[i
])t
[j
]=r
[start
[i
]+j
-1];
t
[len
[i
]+1]='$';
rep(j
,1,L
)t
[len
[i
]+1+j
]=r
[j
];
kmp
.build(t
,len
[i
]+1+L
);
rep(j
,1,N
)
{
auto pr
= pii(i
,j
);
big
[pr
] = kmp
.next
[len
[i
]+1+start
[j
]+len
[j
]-1];
}
}
int Q
=read();
rep(i
,1,Q
)
{
int a
=read(), b
=read();
if(big
.find(pii(b
,a
))!=big
.end())
{
printf("%d\n",big
[pii(b
,a
)]);
}
else
{
rep(j
,1,len
[b
])t
[j
]=r
[start
[b
]+j
-1];
t
[len
[b
]+1]='|';
int tot
= len
[b
]+1;
rep(j
,max(start
[a
],start
[a
]+len
[a
]-1-len
[b
]+1),start
[a
]+len
[a
]-1)
t
[++tot
]=r
[j
];
kmp
.build(t
,tot
);
printf("%d\n",kmp
.next
[tot
]);
}
}
return 0;
}
