Liveddd's Blog

愛にできることはまだあるかい

LOJ#2720. 「NOI2018」你的名字

发表于 更新于 分类于
本文字数： 8.2k 阅读时长 ≈ 18 分钟

经典的字符串题目，但是感觉有些套路。

先考虑 $l=1,r=n$ 的情况，似乎很经典。我们分别对 $S,T$ 建 SAM，尝试对于每个 $T$ 的前缀求在 $S$ 中出现过的最长后缀。设当前最长公共子串在 SAM 上状态为 $u$，其长度为 $len$。考虑下一位 $T_i$ 的转移是否存在：

  1. 存在转移 $(u,v,T_i)$，那么 $u\to v$，$len\to len+1$。
  2. 不存在转移 $(u,v,T_i)$，那么状态 $u\to \operatorname{link}(u)$，$len\to \operatorname{len}(link(u))$。重新考虑下一位 $T_i$ 的转移是否存在。

然后对应的在 $T$ 的 parent 树上求出子树 max 后容易得到答案。建出 $S$ 的 SAM 时间复杂度为 $\mathcal O(|S|)$，单次询问的复杂度为 $\mathcal O(|T|)$，可以获得 64 pts。

Code 64pts
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
using ll=long long;
const int N=5e5+10,C=26;
template<class T>
inline void read(T &x)
{
    x=0;int f=0; 
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
struct SAM
{
    struct Node{int fa,len,ne[C];}g[N<<1];
    int tot=1,last=1;
    void init(){tot=1,last=1,g[1]={};}
    void insert(int c)
    {
        int p=last,x=last=++tot;
        g[x]={};
        g[x].len=g[p].len+1;
        while(p&&!g[p].ne[c])
            g[p].ne[c]=x,p=g[p].fa;
        if(!p)return g[x].fa=1,void();
        int q=g[p].ne[c];
        if(g[q].len==g[p].len+1)return g[x].fa=q,void();
        int nq=++tot;
        g[nq]={};
        g[nq]=g[q],g[nq].len=g[p].len+1,g[x].fa=g[q].fa=nq;
        while(p&&g[p].ne[c]==q)
            g[p].ne[c]=nq,p=g[p].fa;
    }
}sams,samt;

int T,n,m;
char s[N];
int maxlen[N],pos[N];
int ord[N<<1],f[N<<1];
vector<int>e[N<<1];
inline void ckmax(int &x,int y){x=x>y?x:y;}
inline void add(int u,int v){e[u].push_back(v);}
inline ll calc()
{
    for(int i=1;i<=samt.tot;i++)e[i].clear();
    for(int i=1;i<=samt.tot;i++)add(samt.g[i].fa,i);
    int l=1,r=1;
    ord[1]=1;
    while(l<=r)
    {
        int x=ord[l++];
        for(auto y:e[x])ord[++r]=y;
    }
    ll res=0;
    for(int i=r;i>1;i--)
    {
        int x=ord[i];
        for(auto y:e[x])ckmax(f[x],f[y]);
        if(f[x]<samt.g[x].len)
            res+=samt.g[x].len-max(f[x],samt.g[samt.g[x].fa].len);
    }
    return res;
}
inline void solve()
{
    int l,r;
    scanf("%s",s+1);
    read(l,r);
    m=strlen(s+1);
    samt.init();
    for(int i=1;i<=m;i++)samt.insert(s[i]-'a'),pos[i]=samt.last;
    for(int i=1;i<=samt.tot;i++)f[i]=0;
    for(int i=1,u=1,len=0;i<=m;i++)
    {
        int c=s[i]-'a';
        while(u>1&&!sams.g[u].ne[c])u=sams.g[u].fa,len=sams.g[u].len;
        if(sams.g[u].ne[c])u=sams.g[u].ne[c],len++;
        f[pos[i]]=len;
    }
    printf("%lld\n",calc());
}

int main()
{
    freopen("name.in","r",stdin);
    freopen("name.out","w",stdout);
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1;i<=n;i++)sams.insert(s[i]-'a');
    read(T);
    while(T--)solve();
    return 0;
}

接下来考虑一般的情况。还是向上面一样在 $S$ 的 SAM 上跑，但是还需要满足匹配的子串在 $S[l,r]$ 中出现过。一个简单的想法是直接求出 所有等价类出现的位置，直接是用线段树合并即可。最终时间复杂度为 $\mathcal O(|S|\log |S|+|T|\log |S|)$。

Code 100pts
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
using ll=long long;
const int N=5e5+10,M=3e7+10,C=26;
template<class T>
inline void read(T &x)
{
    x=0;int f=0; 
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
struct SAM
{
    struct Node{int fa,len,ne[C];}g[N<<1];
    int tot=1,last=1;
    void init(){tot=1,last=1,g[1]={};}
    void insert(int c)
    {
        int p=last,x=last=++tot;
        g[x]={};
        g[x].len=g[p].len+1;
        while(p&&!g[p].ne[c])
            g[p].ne[c]=x,p=g[p].fa;
        if(!p)return g[x].fa=1,void();
        int q=g[p].ne[c];
        if(g[q].len==g[p].len+1)return g[x].fa=q,void();
        int nq=++tot;
        g[nq]={};
        g[nq]=g[q],g[nq].len=g[p].len+1,g[x].fa=g[q].fa=nq;
        while(p&&g[p].ne[c]==q)
            g[p].ne[c]=nq,p=g[p].fa;
    }
}sams,samt;
//SAM
int tot,rt[N<<1];
struct Node
{
    int l,r;
    int cnt;
}tr[M];
void pushup(int x){tr[x].cnt=tr[tr[x].l].cnt+tr[tr[x].r].cnt;}
void insert(int &x,int l,int r,int pos)
{
    if(!x)x=++tot;
    if(l==r)return void(tr[x].cnt++);
    int mid=l+r>>1;
    if(pos<=mid)insert(tr[x].l,l,mid,pos);
    else insert(tr[x].r,mid+1,r,pos);
    pushup(x);
}
int merge(int p,int q,int l,int r)
{
    if(!p||!q)return p|q;
    int x=++tot,mid=l+r>>1;
    if(l==r)return tr[x].cnt=tr[p].cnt+tr[q].cnt,x;
    tr[x].l=merge(tr[p].l,tr[q].l,l,mid);
    tr[x].r=merge(tr[p].r,tr[q].r,mid+1,r);
    pushup(x);
    return x;
}
int query(int x,int l,int r,int ql,int qr)
{
    if(!x||l>qr||r<ql)return 0;
    if(l==r)return l;
    int mid=l+r>>1,res;
    if((res=query(tr[x].r,mid+1,r,ql,qr)))return res;
    return query(tr[x].l,l,mid,ql,qr);
}
//SegmentTree

int T,n,m;
char s[N];
int maxlen[N],pos[N];
int ord[N<<1],f[N<<1];
vector<int>e[N<<1];
inline void ckmax(int &x,int y){x=x>y?x:y;}
inline void add(int u,int v){e[u].push_back(v);}
inline ll calc()
{
    for(int i=1;i<=samt.tot;i++)e[i].clear();
    for(int i=1;i<=samt.tot;i++)add(samt.g[i].fa,i);
    int l=1,r=1;
    ord[1]=1;
    while(l<=r)
    {
        int x=ord[l++];
        for(auto y:e[x])ord[++r]=y;
    }
    ll res=0;
    for(int i=r;i>1;i--)
    {
        int x=ord[i];
        for(auto y:e[x])ckmax(f[x],f[y]);
        if(f[x]<samt.g[x].len)
            res+=samt.g[x].len-max(f[x],samt.g[samt.g[x].fa].len);
    }
    return res;
}
inline void solve()
{
    int l,r;
    scanf("%s",s+1);
    read(l,r);
    m=strlen(s+1);
    samt.init();
    for(int i=1;i<=m;i++)samt.insert(s[i]-'a'),pos[i]=samt.last;
    for(int i=1;i<=samt.tot;i++)f[i]=0;
    for(int i=1,u=1,len=0;i<=m;i++)
    {
        int c=s[i]-'a';
        while(u>1&&(!sams.g[u].ne[c]||query(rt[sams.g[u].ne[c]],1,n,l,r)<l+len))
            if(--len<=sams.g[sams.g[u].fa].len)u=sams.g[u].fa;
        if(sams.g[u].ne[c]&&query(rt[sams.g[u].ne[c]],1,n,l,r)>=l+len)
            u=sams.g[u].ne[c],len++;
        f[pos[i]]=len;
    }
    printf("%lld\n",calc());
}

int main()
{
    freopen("name.in","r",stdin);
    freopen("name.out","w",stdout);
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1;i<=n;i++)sams.insert(s[i]-'a'),pos[i]=sams.last;
    for(int i=1;i<=n;i++)
    {
        int x=pos[i];
        insert(rt[x],1,n,i);
    }
    for(int i=1;i<=sams.tot;i++)add(sams.g[i].fa,i);
    int l=1,r=1;
    ord[1]=1;
    while(l<=r)
    {
        int x=ord[l++];
        for(auto y:e[x])ord[++r]=y;
    }
    for(int i=r;i>1;i--)
    {
        int x=ord[i];
        for(auto y:e[x])rt[x]=merge(rt[x],rt[y],1,n);
    }
    read(T);
    while(T--)solve();
    return 0;
}