后缀自动机部分习题

如果你看了我的上一篇博客，大概已经会写后缀自动机了吧，下面就是一些习题：

Hihocoder1403：

求出现k次的可重叠最长子串。

跑出right集合后用right集合大小>=k的节点的长度更新答案即可。

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 #define debug cout
 7 using namespace std;
 8 const int maxn=4e4+1e2;
 9 
10 int n,m,cnt,ans;
11 int in[maxn];
12 
13 struct Node {
14     Node* par,*nxt[100];
15     int len;
16     long long deg,tme;
17 }ns[maxn],*root,*last;
18 
19 Node* NewNode(int ll) {
20     ns[++cnt].len = ll;
21     return &ns[cnt];
22 }
23 
24 inline void extend(int x) {
25     Node* p = last;
26     Node* np = NewNode(p->len+1);
27     np -> tme = 1;
28     while( p && !p->nxt[x] )
29         p->nxt[x] = np,
30         p = p->par;
31     if( !p )
32         np->par = root;
33     else {
34         Node* q = p->nxt[x];
35         if( q->len == p->len + 1 )
36             np->par = q;
37         else {
38             Node* nq = NewNode(p->len+1);
39             memcpy(nq->nxt,q->nxt,sizeof(q->nxt));
40             nq->par = q->par;
41             q->par = np->par = nq; // ?
42             while( p && p->nxt[x] == q )
43                 p->nxt[x] = nq,
44                 p = p->par;
45         }
46     }
47     last = np;
48 }
49 
50 inline void topo() {
51     for(int i=1;i<=cnt;i++)
52         if( ns[i].par )
53             ++ns[i].par->deg;
54     queue<Node*> q;
55     for(int i=1;i<=cnt;i++)
56         if( !ns[i].deg )
57             q.push(ns+i);
58     while( q.size() ) {
59         const Node* pos = q.front(); q.pop();
60         if( pos == root )
61             break;
62         if( pos->tme >= m ) {
63             ans = max( ans , pos->len );
64         }
65         pos->par->tme += pos->tme;
66         if( !--pos->par->deg )
67             q.push(pos->par);
68     }
69 }
70 
71 int main() {
72     last = root = NewNode(0);
73     root->tme = 0;
74     scanf("%d%d",&n,&m);
75     for(int i=1;i<=n;i++)
76         scanf("%d",in+i);
77     for(int i=1;i<=n;i++)
78         extend(in[i]-1);
79     
80     topo();
81     
82     printf("%d
",ans);
83     
84     return 0;
85 }

View Code

Hihocoder1407：

求出现两次的最长不重叠子串。

先处理出后缀自动机，然后拓扑排序跑出right的最值。用right最值的差和节点代表字符串长度中的min更新答案。

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 #include<map>
 7 #define debug cout
 8 using namespace std;
 9 const int maxn=2.5e5+1e2;
10 const int inf=0x3f3f3f3f;
11 
12 int in[maxn>>1];
13 int n,m,cnt,ans;
14 
15 struct Node {
16     Node *fa;
17     map<int,Node*> nxt;
18     int len,deg,mxr,mir;
19     Node() {
20         mxr = -inf , mir = inf;
21     }
22 }ns[maxn],*root,*last;
23 
24 Node* NewNode(int ll) {
25     ns[++cnt].len = ll;
26     return ns+cnt;
27 }
28 
29 inline void extend(int x,int pp) {
30     Node* p = last;
31     Node* np = NewNode(p->len+1);
32     np->mir = np->mxr = pp;
33     while( p && p->nxt.find(x) == p->nxt.end() )
34         p->nxt[x] = np,
35         p = p->fa;
36     if( !p )
37         np->fa = root;
38     else {
39         Node* q = p->nxt[x];
40         if( q->len == p->len + 1 )
41             np->fa = q;
42         else {
43             Node* nq = NewNode(p->len+1);
44             nq->nxt = q->nxt; // ?
45             nq->fa = q->fa;
46             q->fa = np->fa = nq;
47             while( p && p->nxt[x] == q )
48                 p->nxt[x] = nq,
49                 p = p->fa;
50         }
51     }
52     last = np;
53 }
54 
55 inline void topo() {
56     for(int i=1;i<=cnt;i++)
57         if( ns+i != root )
58             ++ns[i].fa->deg;
59     queue<Node*> q;
60     for(int i=1;i<=cnt;i++)
61         if( !ns[i].deg )
62             q.push(ns+i);
63     while( q.size() ) {
64         const Node* pos = q.front(); q.pop();
65         if( pos == root )
66             break;
67         ans = max( ans , min( pos->len , pos->mxr - pos->mir ) );
68         pos->fa->mir = min( pos->fa->mir , pos->mir );  
69         pos->fa->mxr = max( pos->fa->mxr , pos->mxr );
70         if( !--pos->fa->deg )
71             q.push(pos->fa);
72     }
73 }
74 
75 int main() {
76     scanf("%d",&n);
77     for(int i=1;i<=n;i++)
78         scanf("%d",in+i);
79     
80     last = root = NewNode(0);
81     for(int i=1;i<=n;i++)
82         extend(in[i],i);
83     topo();
84     
85     printf("%d
",ans);
86     
87     return 0;
88 }

View Code

Hihocoder1415：

求两字符串最长公共子串，直接在后缀自动机上匹配即可，用节点的len转移。注意转移分情况讨论正确。

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define debug cout
 6 using namespace std;
 7 const int maxn=2.5e5+1e2;
 8 
 9 char a[maxn],b[maxn];
10 int la,lb,cnt,ans;
11 
12 struct Node {
13     Node *fa,*nxt[26];
14     int len;
15 }ns[maxn],*root,*last;
16 
17 Node* NewNode(int ll) {
18     ns[++cnt].len = ll;
19     return ns+cnt;
20 }
21 
22 inline void extend(int x) {
23     Node* p = last;
24     Node* np = NewNode(p->len+1);
25     while( p && !p->nxt[x] )
26         p->nxt[x] = np,
27         p = p->fa;
28     if( !p )
29         np->fa = root;
30     else {
31         Node* q = p->nxt[x];
32         if( q->len == p->len + 1 )
33             np->fa = q;
34         else {
35             Node* nq = NewNode(p->len+1);
36             memcpy(nq->nxt,q->nxt,sizeof(q->nxt));
37             nq->fa = q->fa;
38             q->fa = np->fa = nq;
39             while( p && p->nxt[x] == q )
40                 p->nxt[x] = nq,
41                 p = p->fa; // ?
42         }
43     }
44     last = np;
45 }
46 
47 inline void getans() {
48     static int len = 0;
49     Node* now = root;
50     for(int i=1;i<=lb;i++) {
51         if( now->nxt[(int)b[i]] )
52             ++len,
53             now = now->nxt[(int)b[i]];
54         else {
55             while( now && !now->nxt[(int)b[i]] )
56                 now = now -> fa;
57             if( !now )
58                 now = root,
59                 len = 0;
60             else
61                 len = now->len + 1,
62                 now = now->nxt[(int)b[i]];
63         }
64         ans = max( ans , len );
65     }
66 }
67 
68 int main() {
69     scanf("%s%s",a+1,b+1);
70     la = strlen(a+1),
71     lb = strlen(b+1);
72     
73     for(int i=1;i<=la;i++)
74         a[i] -= 'a';
75     for(int j=1;j<=lb;j++)
76         b[j] -= 'a';
77     
78     last = root = NewNode(0);
79     for(int i=1;i<=la;i++)
80         extend(a[i]);
81     getans();
82     
83     printf("%d
",ans);
84     
85     return 0;
86 }

View Code

SPOJ LCS：

同Hihocoder1415，再打一遍板子就双倍经验了QAQ。然而SPOJ限定语言必须交g++4.x的那个，否则贡献language error。

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int maxn=5e5+1e2;
 7 
 8 char a[maxn>>1],b[maxn>>1];
 9 int la,lb,cnt,ans;
10 
11 struct Node {
12     Node* fa,*ch[26];
13     int len;
14 }ns[maxn],*root,*last;
15 
16 inline Node* NewNode(int ll) {
17     ns[++cnt].len = ll;
18     return ns + cnt;
19 }
20 
21 inline void extend(int x) {
22     Node* p = last;
23     Node* np = NewNode(p->len+1);
24     while( p && !p->ch[x] )
25         p->ch[x] = np,
26         p = p->fa;
27     if( !p )
28         np->fa = root;
29     else {
30         Node* q = p->ch[x];
31         if( q->len == p->len + 1 )
32             np->fa = q;
33         else {
34             Node* nq = NewNode(p->len+1);
35             memcpy(nq->ch,q->ch,sizeof(q->ch));
36             nq->fa = q->fa;
37             q->fa = np->fa = nq;
38             while( p && p->ch[x] == q )
39                 p->ch[x] = nq,
40                 p = p-> fa;
41         }
42     }
43     last = np;
44 }
45 
46 inline void getans() {
47     int len = 0;
48     Node* now = root;
49     for(int i=1;i<=lb;i++) {
50         const int t = b[i] - 'a';
51         if( now->ch[t] ) {
52             now = now->ch[t],
53             ++len;
54         }
55         else {
56             while( now && !now->ch[t] )
57                 now = now->fa;
58             if( !now )
59                 now = root,
60                 len = 0;
61             else
62                 len = now->len + 1,
63                 now = now->ch[t];
64         }
65         ans = max( ans , len );
66     }
67 }
68 
69 int main() {
70     scanf("%s%s",a+1,b+1);
71     la = strlen(a+1) ,
72     lb = strlen(b+1) ;
73     
74     last = root = NewNode(0);
75     for(int i=1;i<=la;i++)
76         extend(a[i]-'a');
77     
78     getans();
79     
80     printf("%d
",ans);
81     
82     return 0;
83 }

View Code

SPOJ LCS2：

求多个字符串的最长公共子串！

细节坑！就是这个题WA了我半天的！

我们还是选择一个字符串建立后缀自动机(我钦定第一个)然后用其他的去匹配，但是我们不能向前面那样直接更新答案，我们需要在节点上记录每个串在这个节点匹配的最大长度，然后拓扑序向parent转移。最后对于每个节点用每个串匹配的最短值和节点表示串长的min更新答案。

没有对单点单串所有匹配长度取max：wa。

没有与节点长度取min：wa。

没有逆拓扑序列：wa。

最后上代码：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<queue>
  6 #define debug cout
  7 using namespace std;
  8 const int maxn=3e5+1e2;
  9 const int inf=0x3f3f3f3f;
 10 
 11 char a[maxn>>1],b[maxn>>1];
 12 int la,lb,cnt,ans,T;
 13 
 14 struct Node {
 15     Node* fa,*ch[26];
 16     int len,deg,f[12];
 17 }ns[maxn],*root,*last;
 18 
 19 inline Node* NewNode(int ll) {
 20     ns[++cnt].len = ll;
 21     return ns + cnt;
 22 }
 23 
 24 inline void extend(int x) {
 25     Node* p = last;
 26     Node* np = NewNode(p->len+1);
 27     while( p && !p->ch[x] )
 28         p->ch[x] = np,
 29         p = p->fa;
 30     if( !p )
 31         np->fa = root;
 32     else {
 33         Node* q = p->ch[x];
 34         if( q->len == p->len + 1 )
 35             np->fa = q;
 36         else {
 37             Node* nq = NewNode(p->len+1);
 38             memcpy(nq->ch,q->ch,sizeof(q->ch));
 39             nq->fa = q->fa;
 40             q->fa = np->fa = nq;
 41             while( p && p->ch[x] == q )
 42                 p->ch[x] = nq,
 43                 p = p-> fa;
 44         }
 45     }
 46     last = np;
 47 }
 48 
 49 inline void getans() {
 50     int len = 0;
 51     Node* now = root;
 52     for(int i=1;i<=lb;i++) {
 53         const int t = b[i] - 'a';
 54         if( now->ch[t] ) {
 55             now = now->ch[t],
 56             ++len;
 57         }
 58         else {
 59             while( now && !now->ch[t] )
 60                 now = now->fa;
 61             if( !now )
 62                 now = root,
 63                 len = 0;
 64             else
 65                 len = now->len + 1,
 66                 now = now->ch[t];
 67         }
 68         now->f[T] = max( now->f[T] , len );
 69     }
 70 }
 71 inline void cunt() {
 72     for(int i=1;i<=cnt;i++)
 73         if( ns[i].fa )
 74             ++ns[i].fa->deg;
 75     queue<Node*> q;
 76     for(int i=1;i<=cnt;i++)
 77         if( !ns[i].deg )
 78             q.push(ns+i);
 79     while( q.size() ) {
 80         const Node* pos = q.front(); q.pop();
 81         if( pos == root )
 82             break;
 83         for(int i=1;i<=T;i++)
 84             pos->fa->f[i] = max( pos->fa->f[i] , pos->f[i] );
 85         if( !--pos->fa->deg )
 86             q.push(pos->fa);
 87     }
 88     for(int i=1,nw;i<=cnt;i++) {
 89         if( ns + i == root )
 90             continue;
 91         nw = inf;
 92         for(int j=1;j<=T;j++)
 93             nw = min( nw , ns[i].f[j] );
 94         nw = min( nw , ns[i].len ); // ?
 95         ans = max( ans , nw );
 96     }
 97 }
 98 
 99 int main() {
100     scanf("%s",a+1);
101     la = strlen(a+1) ,
102     
103     last = root = NewNode(0);
104     for(int i=1;i<=la;i++)
105         extend(a[i]-'a');
106     
107     while( scanf("%s",b+1) == 1 ) {
108         ++T;
109         lb = strlen(b+1);
110         getans();
111     }
112     
113     cunt();
114     
115     printf("%d
",ans);
116     
117     return 0;
118 }

View Code