NC17495. 后缀自动鸡
描述
输入描述
第一行一个串 s。
第二行一个正整数 q。表示询问个数。
接下来 q 行每行一个数 k(1<=k<=|s|)，表示一个询问 k（意义如上）。其中|s|表示 s 的长度。
输出描述
每行依次为字典序最小的拥有最多的不同的子串、一个空格、符合条件的串拥有的不同子串个数。
示例1
输入:
baa 2 2 1
输出:
ba 3 a 1
示例2
输入:
ajddbijcebifijibhcfbicbegggfdedbahhcecbbfhabhdiedfjjbbbgcgebahhjehbigaeijehdjhbciaajhdcacgdiggegahbi 10 51 59 45 1 47 85 33 51 83 9
输出:
bifijibhcfbicbegggfdedbahhcecbbfhabhdiedfjjbbbgcgeb 1277 ajddbijcebifijibhcfbicbegggfdedbahhcecbbfhabhdiedfjjbbbgcge 1709 bfhabhdiedfjjbbbgcgebahhjehbigaeijehdjhbciaaj 994 a 1 cbbfhabhdiedfjjbbbgcgebahhjehbigaeijehdjhbciaaj 1084 jcebifijibhcfbicbegggfdedbahhcecbbfhabhdiedfjjbbbgcgebahhjehbigaeijehdjhbciaajhdcacgd 3554 bfhabhdiedfjjbbbgcgebahhjehbigaei 537 bifijibhcfbicbegggfdedbahhcecbbfhabhdiedfjjbbbgcgeb 1277 bifijibhcfbicbegggfdedbahhcecbbfhabhdiedfjjbbbgcgebahhjehbigaeijehdjhbciaajhdcacgdi 3388 abhdiedfj 44
说明:
|s|≤100000,q≤10,1≤k≤|s|C++14(g++5.4) 解法, 执行用时: 116ms, 内存消耗: 34096K, 提交时间: 2020-10-08 18:49:55
/*
* @Author : Nightmare
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ls 2 * rt
#define rs 2 * rt + 1
#define gcd(a,b) __gcd(a,b)
#define eps 1e-8
#define lowbit(x) (x&(-x))
#define N 200005
#define M 10
#define mod 1000000007
#define inf 0x3f3f3f3f
struct SAM{
static const int maxn = 2e5 + 5;
int nxt[maxn][26], fail[maxn], fa[maxn], len[maxn], endpos[maxn];
int root, tot, last, n; ll f[maxn], g[maxn];
int ch[maxn][2];
inline int newnode(int l){
ch[tot][0] = ch[tot][1] = 0;
fa[tot] = fail[tot] = -1; endpos[tot] = -1;
for(int i = 0 ; i < 26 ; i ++) nxt[tot][i] = -1;
len[tot ++] = l;
return tot - 1;
}
inline void init(int mx){
tot = 0; n = mx;
for(int i = 1 ; i <= n ; i ++) f[i] = g[i] = 0;
last = root = newnode(0);
}
inline void insert(int x, int id){
int p = last, np = newnode(len[p] + 1);
last = np; endpos[np] = id;
while(p != -1 && nxt[p][x] == -1) nxt[p][x] = np, p = fa[p];
if(p == -1) fa[np] = root;
else{
int q = nxt[p][x];
if(len[q] == len[p] + 1) fa[np] = q;
else{
int nq = newnode(len[p] + 1);
memcpy(nxt[nq], nxt[q], sizeof(nxt[q]));
fa[nq] = fa[q]; fa[q] = fa[np] = nq;
while(p != -1 && nxt[p][x] == q) nxt[p][x] = nq, p = fa[p];
}
}
}
inline void build(){
for(int i = 0 ; i < tot ; i ++) fail[i] = fa[i];
}
inline int dir(int x){
return ch[fa[x]][1] == x;
}
inline bool isroot(int x){
return ch[fa[x]][0] != x && ch[fa[x]][1] != x;
}
inline void rotate(int x){
int y = fa[x], z = fa[y], k = dir(x);
if(!isroot(y)) ch[z][ch[z][1] == y] = x;
else endpos[x] = endpos[y];
ch[y][k] = ch[x][k ^ 1]; fa[ch[y][k]] = y;
ch[x][k ^ 1] = y; fa[y] = x; fa[x] = z;
}
inline void splay(int x){
for(int y = fa[x] ; !isroot(x) ; y = fa[x]){
if(!isroot(y)) dir(y) == dir(x) ? rotate(y) : rotate(x);
rotate(x);
}
}
inline int access(int x){
int p = 0;
update(1, endpos[x], 1);
while(x){
splay(x);
endpos[ch[x][1]] = endpos[x];
ch[x][1] = p;
if(p){
if(endpos[x] != -1)
update(endpos[x] - len[x] + 1, endpos[x] - len[fa[x]], -1);
endpos[x] = endpos[p];
}
p = x; x = fa[x];
}
return p;
}
inline void update(int l, int r, int v){
r ++;
for(int i = l ; i <= n ; i += lowbit(i)) f[i] += v, g[i] += l * v;
for(int i = r ; i <= n ; i += lowbit(i)) f[i] -= v, g[i] -= r * v;
}
inline ll query(int l, int r){
ll ans = 0; l --;
for(int i = l ; i > 0 ; i -= lowbit(i)) ans -= f[i] * (l + 1), ans += g[i];
for(int i = r ; i > 0 ; i -= lowbit(i)) ans += f[i] * (r + 1), ans -= g[i];
return ans;
}
}sam;
struct suffix_array {
static const int maxn = 2e5 + 5;
int sa[maxn], h[maxn], c[maxn], y[maxn], rk[maxn], str[maxn];
inline void init(char *s, int n){
for(int i = 0 ; i < n ; i ++) str[i] = s[i + 1] - 'a' + 1;
str[n] = 0;
}
void build(int n, int m) {
for (int i = 0; i < m; i++) c[i] = 0;
for (int i = 0; i < n; i++) c[rk[i] = str[i]]++;
for (int i = 1; i < m; i++) c[i] += c[i - 1];
for (int i = n - 1; i >= 0; i--) sa[--c[rk[i]]] = i;
for (int k = 1; k < n; k <<= 1) {
int num = 0;
for (int i = n - k; i < n; i++) y[num++] = i;
for (int i = 0; i < n; i++) if (sa[i] >= k) y[num++] = sa[i] - k;
for (int i = 0; i < m; i++) c[i] = 0;
for (int i = 0; i < n; i++) c[rk[i]]++;
for (int i = 1; i < m; i++) c[i] += c[i - 1];
for (int i = n - 1; i >= 0; i--) sa[--c[rk[y[i]]]] = y[i];
swap(rk, y); rk[sa[0]] = 0; num = 1;
for (int i = 1; i < n; i++)
rk[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? num - 1 : num++);
if (num >= n) break;
m = num;
}
for (int i = 0; i < n; i++) rk[sa[i]] = i;
}
}sa;
int k[M], n, Q;
ll ans[M][N];
char s[N];
void out(int l, int r){
char ch = s[r];
s[r] = '\0';
printf("%s", s + l);
s[r] = ch;
}
inline void solve(){
scanf("%s", s + 1); n = strlen(s + 1); sam.init(n);
for(int i = 1 ; i <= n ; i ++) sam.insert(s[i] - 'a', i);
sa.init(s, n);
sam.build();
sa.build(n + 1, 27);
scanf("%d", &Q);
for(int i = 0 ; i < Q ; i ++) scanf("%d", &k[i]);
for(int i = 1, u = sam.root ; i <= n ; i ++){
while(sam.nxt[u][s[i] - 'a'] == -1) u = sam.fail[u];
u = sam.nxt[u][s[i] - 'a'];
sam.access(u);
for(int j = 0 ; j < Q ; j ++)
if(i >= k[j])
ans[j][i - k[j] + 1] = sam.query(i - k[j] + 1, i);
}
for(int i = 0 ; i < Q ; i ++){
int pos = 1;
for(int j = 2 ; j + k[i] - 1 <= n ; j ++){
if(ans[i][j] > ans[i][pos]) pos = j;
else if(ans[i][j] == ans[i][pos]){
if(sa.rk[j - 1] < sa.rk[pos - 1])
pos = j;
}
}
out(pos, pos + k[i]);
printf(" %lld\n", ans[i][pos]);
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("D:\\in.txt", "r", stdin);
#endif
solve();
#ifndef ONLINE_JUDGE
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 556ms, 内存消耗: 97040K, 提交时间: 2018-08-03 21:44:34
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define sz(x) (int((x).size()))
typedef long long LL;
const int MX=100005;
const int MC=26;
inline int get(char c)
{
return c-'a';
}
struct Node;
typedef Node* PNode;
struct Node
{
int l,r,pardp,ccnt;
PNode par,slink;
PNode chd[MC];
inline int len()
{
return r-l;
}
inline int depth()
{
return pardp+len();
}
inline bool inEdge(int pos)
{
return pardp<=pos&&pos<depth();
}
bool DFS();
};
struct SuffixTree
{
char*s;
int dn,sn,jj;
bool needWalk;
PNode root,cur,need;
Node d[MX*2];
queue<PNode>que;
LL tot;
PNode newNode()
{ d[dn]=Node();
return&d[dn++];
}
void add_edge(PNode p,PNode q,int l,int r)
{
p->chd[get(s[l])]=q;
p->ccnt++;
q->par=p;
q->pardp=p->depth();
q->l=l,q->r=r;
}
void walk_down(int j,int i)
{
if(i<j) return;
for(int h=j+cur->depth();!(cur->inEdge(i-j));h+=cur->len())cur=cur->chd[get(s[h])];
}
void add_slink()
{
if(need)need->slink=cur;
need=0;
}
void extend(int i)
{
int k,pos;
char c=s[i+1];
PNode leaf,split;
for(;jj<=i+1;jj++)
{
if(needWalk)
{
if(!cur->slink&&cur->par)cur=cur->par;
cur=(cur->slink)?cur->slink:root;
walk_down(jj,i);
}
needWalk=1;
k=i-jj+1;
if(k==cur->depth())
{
add_slink();
if(cur->chd[get(c)])
{
cur=cur->chd[get(c)];
needWalk=0;
break;
}
leaf=newNode();
add_edge(cur,leaf,i+1,sn);
que.push(leaf);
}
else
{
pos=cur->l+(k-cur->pardp);
if(s[pos]==c)
{
add_slink();
if(pos!=i+1)
{
needWalk=0;
break;
}
}
else
{
split=newNode();
leaf=newNode();
add_edge(cur->par,split,cur->l,pos);
cur->par->ccnt--;
add_edge(split,cur,pos,cur->r);
add_edge(split,leaf,i+1,sn);
que.push(leaf);
cur=split;
add_slink();
if(cur->depth()==1)cur->slink=root;
else need=cur;
}
}
}
tot+=sz(que);
}
void erase(int i)
{
int k;
PNode tmp;
tmp=que.front();
que.pop();
while(!(tmp->ccnt))
{
if(cur==tmp)
{
k=(i-jj+1)-cur->pardp;
tot-=min(cur->r,i+1)-cur->l-k;
cur->l=i+1-k;
cur->r=sn;
que.push(cur);
break;
}
tmp->par->chd[get(s[tmp->l])]=0;
tmp->par->ccnt--;
tot-=min(tmp->r,i+1)-tmp->l;
tmp=tmp->par;
}
if(!(tmp->ccnt))
{
cur=cur->par;
if(cur!=root)cur=cur->slink;
walk_down(++jj,i);
needWalk=0;
}
}
void init(char *t,int tn)
{
s=t,sn=tn;
dn=0;
root=newNode();
cur=newNode();
add_edge(root,cur,0,sn);
need=0;
jj=1;
needWalk=1;
while(!que.empty())que.pop();
que.push(cur);
tot=1;
}
void build(char*t,int tn)
{
init(t,tn);
for(int i=0;i<tn-1;i++)extend(i);
}
};
char s[MX];
int n,k;
SuffixTree t1,t2;
LL a[MX],ans;
int st;
bool Node::DFS()
{
if(!ccnt)
{
if(depth()<k) return 0;
st=n-depth();
return a[st]==ans;
}
for(int i=0;i<MC;i++)
{
PNode p=chd[i];
if(!p)continue;
if(p->DFS()) return 1;
}
return 0;
}
int main()
{
int q,i;char c;
scanf("%s",s);
{ n=strlen(s);
t1.build(s,n);
for(scanf("%d",&q);q--;)
{ scanf("%d",&k);
t2.init(s,n);
for(i=0;i<k-1;i++)t2.extend(i);
a[0]=t2.tot;
for(i=k;i<n;i++)
{ t2.extend(i-1);
t2.erase(i);
a[i-k+1]=t2.tot;
}
ans=*max_element(a,a+n-k+1);
st=-1;
t1.root->DFS();
c=s[st+k];
s[st+k]=0;
printf("%s %lld\n",s+st,ans);
s[st+k]=c;
}
}
return 0;
}