http://www.spoj.com/problems/SUBLEX/
好難啊。
建出后綴自動機，然后在后綴自動機的每個狀態上記錄通過這個狀態能走到的不同子串的數量。該狀態能走到的所有狀態的f值的和+1就是當前狀態的f值。
最后對于詢問的k，從root開始走順便加加減減就可以了。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int in() {int k = 0; char c = getchar();for(; c < '0' || c > '9'; c = getchar());for(; c >= '0' && c <= '9'; c = getchar())k = k * 10 + c - 48;return k;
}int tot = 0, par[250003], go[250003][26], val[250003], f[250003], root, last;void extend(int w) {int p = last;int np = ++tot; val[np] = val[p] + 1;while (p && go[p][w] == 0)go[p][w] = np, p = par[p];if (p == 0) par[np] = root;else {int q = go[p][w];if (val[q] == val[p] + 1) par[np] = q;else {int nq = ++tot; val[nq] = val[p] + 1;memcpy(go[nq], go[q], sizeof(go[q]));par[nq] = par[q];par[q] = par[np] = nq;while (p && go[p][w] == q)go[p][w] = nq, p = par[p];}}last = np;
}char s[150003];
int len, Q, k, c[150003], id[250003], tmp;int main() {root = last = ++tot;scanf("%s", s + 1);len = strlen(s + 1);for(int i = 1; i <= len; ++i)extend(s[i] - 'a');for(int i = 1; i <= tot; ++i)++c[val[i]];for(int i = 1; i <= len; ++i)c[i] += c[i - 1];for(int i = tot; i >= 1; --i)id[c[val[i]]--] = i;int sum, x;for(int i = tot; i >= 1; --i) {sum = 0; x = id[i];for(int j = 0; j < 26; ++j)sum += f[go[x][j]];f[x] = sum + 1;}Q = in();while (Q--) {k = in();tmp = root;while (k) {for(int i = 0; i < 26; ++i)if (x = go[tmp][i])if (f[x] >= k) {putchar('a' + i);--k;tmp = x;break;} elsek -= f[x];}puts("");}return 0;
}
轉載于:https://www.cnblogs.com/abclzr/p/5934151.html
總結
以上是生活随笔為你收集整理的【SPOJ 7258】Lexicographical Substring Search的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
