【BZOJ3998】弦论 [SAM]

弦论

Time Limit: 10 Sec Memory Limit: 256 MB
[Submit][Status][Discuss]

Description

　　对于一个给定长度为N的字符串，求它的第K小子串是什么。

Input

　　第一行是一个仅由小写英文字母构成的字符串S。
　　第二行为两个整数T和K，T为0则表示不同位置的相同子串算作一个。
　　T=1则表示不同位置的相同子串算作多个。K的意义如题所述。

Output

　　输出仅一行，为一个数字串，为第K小的子串。如果子串数目不足K个，则输出-1

Sample Input

　　aabc
　　0 3

Sample Output

　　aab

HINT

　　N<=5*10^5, T<2, K<=10^9

Solution

　　首先我们先构造一个后缀自动机，然后分类讨论：

　　1. 如果T=0，点权为1。为什么呢？一个点有一个Right集合，一个Right集合可以表达多个子串 ，然后我们一个点 -> 另外一个点其实不止一条边，我们每条边涵盖了一个信息，意味着 这个点->(走这条边)->到达了下一个点 通过这条边得到的那个新子串，而这多个新子串构成了一个新的点。所以一条合法的路径，就表达了一个子串。

　　2. 如果T=1，点权为Right集合大小。Right集合是结束位置的合集，那么Right集合大小就表示这条路径表达的这个子串出现了多少次。

Code

 #include<iostream>

 #include<string>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 using namespace std;

 typedef long long s64;

 const int ONE = 2e6+;

 int n,T,k;

 char ch[];

 inline int get()

 {

         int res=,Q=;  char c;

         while( (c=getchar())< || c>)

         if(c=='-')Q=-;

         if(Q) res=c-;

         while((c=getchar())>= && c<=)

         res=res*+c-;

         return res*Q;

 }

 struct SAM

 {

         int v[], q[ONE], num[ONE], size[ONE];

         int a[ONE][], len[ONE], fa[ONE], New;

         int last, cnt;

         SAM() {last = cnt = ;}

         void Add(int c)

         {

             int x=last, New=last=++cnt;

             len[New] = len[x] + ;

             num[New] = ;

             while(x && !a[x][c]) a[x][c] = New, x = fa[x];

             if(!x) {fa[New] = ; return;}

             int q = a[x][c];

             if(len[x] +  == len[q]) fa[New] = q;

             else

             {

                 int Nq = ++cnt; len[Nq] = len[x] + ;

                 memcpy(a[Nq], a[q], sizeof(a[q]));

                 fa[Nq] = fa[q];

                 fa[New] = fa[q] = Nq;

                 while(a[x][c] == q) a[x][c] = Nq, x = fa[x];

             }

         }

         void Update()

         {

             for(int i=;i<=cnt;i++) v[len[i]]++;

             for(int i=;i<=n;i++) v[i] += v[i-];

             for(int i=cnt;i>=;i--) q[v[len[i]]--] = i;

             for(int i=cnt; i>=; i--)

             {

                 int x = q[i];

                 if(!T) num[x] = ; else num[fa[x]] += num[x];

             }

             num[] = ;

             for(int i=cnt; i>=; i--)

             {

                 int x = q[i];

                 size[x] = num[x];

                 for(int j=; j<=; j++)

                     size[x] += size[a[x][j]];

             }

         }

         void Dfs(int u,int k)

         {

             if(k <= num[u]) return;

             k -= num[u];

             for(int j=; j<=; j++)

             if(a[u][j])

             {

                 if(k > size[a[u][j]]) k -= size[a[u][j]];

                 else

                 {

                     printf("%c",j+'a'-);

                     Dfs(a[u][j], k);

                     return;

                 }

             }

         }

 }S;

 int main()

 {

         scanf("%s",ch+); n = strlen(ch+);

         T = get();    k = get();

         for(int i=;i<=n;i++) S.Add(ch[i]-'a'+);

         S.Update();

         if(k > S.size[]) printf("-1");

         else S.Dfs(, k);

 }

巴特西