CodeForces 128B String 后缀数组 或 优先队列维护 求第K小子串

 /* * Author: Gatevin
    
  * Created Time:  2015/2/14 19:36:27
    
  * File Name: Mononobe_Mitsuki.cpp
    
  */
    
 #include<iostream>
    
 #include<sstream>
    
 #include<fstream>
    
 #include<vector>
    
 #include<list>
    
 #include<deque>
    
 #include<queue>
    
 #include<stack>
    
 #include<map>
    
 #include<set>
    
 #include<bitset>
    
 #include<algorithm>
    
 #include<cstdio>
    
 #include<cstdlib>
    
 #include<cstring>
    
 #include<cctype>
    
 #include<cmath>
    
 #include<ctime>
    
 #include<iomanip>
    
 using namespace std;
    
 const double eps(1e-8);
    
 typedef long long lint;
    
  
    
 #define maxn 100010
    
  
    
 int wa[maxn], wb[maxn], wv[maxn], Ws[maxn];
    
  
    
 int cmp(int *r, int a, int b, int l)
    
 {
    
     return r[a] == r[b] && r[a + l] == r[b + l];
    
 }
    
  
    
 void da(int *r, int *sa, int n, int m)
    
 {
    
     int *x = wa, *y = wb, *t, i, j, p;
    
     for(i = 0; i < m; i++) Ws[i] = 0;
    
     for(i = 0; i < n; i++) Ws[x[i] = r[i]]++;
    
     for(i = 1; i < m; i++) Ws[i] += Ws[i - 1];
    
     for(i = n - 1; i >= 0; i--) sa[--Ws[x[i]]] = i;
    
     for(j = 1, p = 1; p < n; j *= 2, m = p)
    
     {
    
     for(p = 0, i = n - j; i < n; i++) y[p++] = i;
    
     for(i = 0; i < n; i++) if(sa[i] >= j) y[p++] = sa[i] - j;
    
     for(i = 0; i < n; i++) wv[i] = x[y[i]];
    
     for(i = 0; i < m; i++) Ws[i] = 0;
    
     for(i = 0; i < n; i++) Ws[wv[i]]++;
    
     for(i = 1; i < m; i++) Ws[i] += Ws[i - 1];
    
     for(i = n - 1; i >= 0; i--) sa[--Ws[wv[i]]] = y[i];
    
     for(t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i++)
    
         x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
    
     }
    
     return;
    
 }
    
  
    
 int rank[maxn], height[maxn];
    
 void calheight(int *r, int *sa, int n)
    
 {
    
     int i, j, k = 0;
    
     for(i = 1; i <= n; i++) rank[sa[i]] = i;
    
     for(i = 0; i < n; height[rank[i++]] = k)
    
     for(k ? k-- : 0, j = sa[rank[i] - 1]; r[i + k] == r[j + k]; k++);
    
     return;
    
 }
    
  
    
 char in[maxn];
    
 int s[maxn], sa[maxn];
    
 int K;
    
 int a[maxn];
    
  
    
 void findK(int n)//寻找第K小的子串
    
 {
    
     memset(a, 0, sizeof(a));
    
     int r = 1;
    
     while(K)
    
     {
    
     a[r]++;
    
     if(a[r] > n - sa[r])//后缀sa[r]已经不能提供下一个子串
    
     {
    
         r++;
    
         continue;
    
     }
    
     K--;
    
     /* * 由于后缀sa[r]提供了长度为a[r]的子串, 所有相同子串需要扫描一遍
    
      * 这里height[j] >= a[r]利用到了RMQ的性质,说明可以提供此长度的LCP
    
      */
    
     for(int j = r + 1; j <= n && height[j] >= a[r] && K; j++)
    
         a[j]++, K--;
    
     }
    
     for(int i = 0; i < a[r]; i++)//输出第K子串
    
     printf("%c", in[sa[r] + i]);
    
     printf("\n");
    
     return;
    
 }
    
  
    
 int main()
    
 {
    
     scanf("%s%d", in, &K);
    
     int n = strlen(in);
    
     lint kinds = (lint)n*((lint)n + 1LL)/2LL;
    
     if(kinds < K)//子串总数做比较
    
     {
    
     printf("No such line.\n");
    
     return 0;
    
     }
    
     for(int i = 0; i < n; i++)
    
     s[i] = in[i] - 'a' + 1;
    
     s[n] = 0;
    
     da(s, sa, n + 1, 27);
    
     calheight(s, sa, n);
    
     findK(n);
    
     return 0;
    
 }

 /* * Author: Gatevin
    
  * Created Time:  2015/2/14 18:57:03
    
  * File Name: Mononobe_Mitsuki.cpp
    
  */
    
 #include<iostream>
    
 #include<sstream>
    
 #include<fstream>
    
 #include<vector>
    
 #include<list>
    
 #include<deque>
    
 #include<queue>
    
 #include<stack>
    
 #include<map>
    
 #include<set>
    
 #include<bitset>
    
 #include<algorithm>
    
 #include<cstdio>
    
 #include<cstdlib>
    
 #include<cstring>
    
 #include<cctype>
    
 #include<cmath>
    
 #include<ctime>
    
 #include<iomanip>
    
 using namespace std;
    
 const double eps(1e-8);
    
 typedef long long lint;
    
  
    
 char in[100010];
    
 int K;
    
  
    
 struct node
    
 {
    
     string value;
    
     int next;
    
     node(string v, int n)
    
     {
    
     value = v, next = n;
    
     }
    
     friend bool operator < (node a, node b)
    
     {
    
     return a.value > b.value;//写大于号才是小的优先...
    
     }
    
 };
    
  
    
 int main()
    
 {
    
     scanf("%s", in);
    
     scanf("%d", &K);
    
     int len = strlen(in);
    
     priority_queue <node> Q;
    
     for(int i = 0; i < len; i++)
    
     {
    
     string tmp = "";
    
     tmp.push_back(in[i]);
    
     //话说这里string tmp = "" + in[i]为什么会得到一堆奇怪的结果...
    
     Q.push(node(tmp, i + 1));
    
     }
    
     lint kinds = (lint)len*((lint)len + 1LL)/2LL;
    
     if(kinds < K)
    
     {
    
     printf("No such line.\n");
    
     return 0;
    
     }
    
     while(K)//考虑到K <= 10^5最多只有10^5次出队和入队操作
    
     {
    
     node now = Q.top();
    
     Q.pop();
    
     K--;
    
     if(!K)
    
     {
    
         printf("%s\n", now.value.c_str());
    
         return 0;
    
     }
    
     if(now.next != len)
    
     {
    
         now.value += in[now.next];
    
         now.next++;
    
         Q.push(now);
    
         //Q.push(node(now.value + in[now.next], now.next + 1));如果这么写耗时将增加约700ms..
    
     }
    
     }
    
     return 0;
    
 }