题目描述
求一个串的第k小子串，不同位置的相同的子串算作一个或多个。题解
看到子串就会想到后缀自动机，其实这个题只是一个后缀自动机的简单应用，只要运用一个搜索树的思想找第k个子串即可。
如果重复的子串算作一个的话，那就不用求endpos，直接设为1即可。否则就要求出endpos。 至于如何求某个节点x“后面”的子串数tot，就只用对tot[trans[x][i]]求和即可。 Code
#include#include #include const int M = 1e6 + 10;const int N = 5e5 + 10;char s[N];int trans[M][26], slink[M], maxlen[M], minlen[M], gr[M], ep[M], tot[M];int len, n;int tmp[N], rnk[M];int t, k;inline int new_state(int mx, int mn, int *tr, int sl) { maxlen[n] = mx; minlen[n] = mn; slink[n] = sl; for (int i = 0; i < 26; ++i) { if (tr == NULL) trans[n][i]=-1; else trans[n][i] = tr[i]; } return n++;}inline void link(int x, int y) { minlen[x] = maxlen[y]+1; slink[x] = y; deg[y]++;}inline int addc(int c, int u) { int z = new_state(maxlen[u]+1, -1, NULL, -1); gr[z] = 1; while (u != -1 && trans[u][c] == -1) { trans[u][c] = z; u = slink[u]; } if (u == -1) { link(z, 0); return z; } int x = trans[u][c]; if (maxlen[x] == maxlen[u]+1) { link(z, x); return z; } int y = new_state(maxlen[u]+1, minlen[x], trans[x], slink[x]); link(x, y); link(z, y); while (u != -1 && trans[u][c] == x) { trans[u][c] = y; u = slink[u]; } return z;}inline void build() { int u = new_state(0, 0, NULL, -1); for (int i = 0; i < len; ++i) u = addc(s[i]-'a', u); for (int i = 0; i < n; ++i) tmp[maxlen[i]]++; for (int i = 1; i <= len; ++i) tmp[i] += tmp[i-1]; for (int i = 0; i < n; ++i) rnk[tmp[maxlen[i]]--] = i; for (int i = n; i; --i) { int &j = rnk[i]; ep[j] += gr[j]; if (!t) ep[j] = 1; else if (slink[j] != -1) ep[slink[j]] += ep[j]; } ep[0] = 0; for (int i = n; i; --i) { int &j = rnk[i]; tot[j] = ep[j]; for (int c = 0; c < 26; ++c) if (trans[j][c] != -1) tot[j] += tot[trans[j][c]]; }}int main() { scanf("%s", s); len = strlen(s); scanf("%d%d", &t, &k); build(); int x = 0; if (k > tot[0]) { puts("-1"); return 0; } while (1) { for (int i = 0; i < 26; ++i) if (trans[x][i] != -1) { int &y = trans[x][i]; if (k <= tot[y]) { printf("%c", i+'a'); if (k <= ep[y]) return 0; k -= ep[y]; x = y; break; } else k -= tot[y]; } } return 0;}