SPOJ - SUBLEX Lexicographical Substring Search

感觉后缀自动机好难啊，比后缀数组难多了...看了好几天勉强懂了一丢丢

学习博客：

洛谷某大佬

HihoCoder

题目传送门：https://www.spoj.com/problems/SUBLEX/en/

题意：给你一个字符串，然后是q次查询，每次输出第i小的字符串。

题解：先构造出后缀自动机，然后对每个节点预处理出从这个节点可以到达多少个不同的子串，然后沿着SAM一路查找下去并更新。

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 
  4 const int maxn=2e6+10;
  5 
  6 struct state
  7 {
  8     int mxlen,link;
  9     int cnt;
 10     int nt[26];
 11 }st[maxn<<1];
 12 
 13 int sz,last;
 14 char s[maxn];
 15 
 16 inline void sam_init()
 17 {
 18    st[0].mxlen=0;
 19    st[0].link=-1;
 20    sz=1;
 21    last=0;
 22 }
 23 
 24 inline void sam_extend(int c)
 25 {
 26     c-='a';
 27     int cur=sz++;
 28     st[cur].mxlen=st[last].mxlen+1;
 29     st[cur].cnt=1;
 30     int p=last;
 31     while(p!=-1&&!st[p].nt[c]){
 32         st[p].nt[c]=cur;
 33         p=st[p].link;
 34     }
 35     if(p==-1) st[cur].link=0;
 36     else{
 37         int q=st[p].nt[c];
 38         if(st[p].mxlen+1==st[q].mxlen) st[cur].link=q;
 39         else{
 40             int clone=sz++;
 41             st[clone].mxlen=st[p].mxlen+1;
 42             memcpy(st[clone].nt,st[q].nt,sizeof(st[q].nt));
 43             st[clone].link=st[q].link;
 44             while(p!=-1&&st[p].nt[c]==q){
 45                 st[p].nt[c]=clone;
 46                 p=st[p].link;
 47             }
 48             st[q].link=st[cur].link=clone;
 49         }
 50     }
 51     last=cur;
 52 }
 53 
 54 int b[maxn],c[maxn];
 55 
 56 void build()        //这个难道不是基排吗，为啥看好多博客写拓扑排序,,,
 57 {
 58     int len=strlen(s+1);
 59     for(int i=1;i<=len;i++) sam_extend(s[i]);
 60     for(int i=1;i<=sz;i++) c[st[i].mxlen]++;
 61     for(int i=1;i<=sz;i++) c[i]+=c[i-1];
 62     for(int i=1;i<=sz;i++) b[c[st[i].mxlen]--]=i;
 63     for(int i=sz;i>=1;i--){
 64         st[b[i]].cnt=1;
 65         for(int j=0;j<26;j++)
 66             st[b[i]].cnt+=st[st[b[i]].nt[j]].cnt;     //st[].cnt记录当前节点不同子串个数
 67     }
 68 }
 69 
 70 void query(int k)
 71 {
 72     int p=0;
 73     while(k){
 74         for(int i=0;i<26;i++){
 75             if(st[p].nt[i]){
 76                 if(k>st[st[p].nt[i]].cnt) k-=st[st[p].nt[i]].cnt;
 77                 else {
 78                     char ch=i+'a';
 79                     cout<<ch;
 80                     p=st[p].nt[i];
 81                     k--;
 82                     break;
 83                 }
 84             }
 85         }
 86     }
 87 }
 88 
 89 int main()
 90 {
 91     ios::sync_with_stdio(false);
 92     cin.tie(0);
 93     cout.tie(0);
 94     cin>>s+1;
 95     sam_init();
 96     build();
 97     int m;
 98     cin>>m;
 99     while(m--){
100         int n;
101         cin>>n;
102         query(n);
103         cout<<endl;
104     }
105     return 0;
106 }

有一个地方我一直没搞清楚，这两种写法不一样吗？一种是父亲加上他，一种是它加儿子，最后结果应该是一样的吧...但是第一种写法是错的。

SPOJ - SUBLEX Lexicographical Substring Search

全站热榜