2019年icpc徐州站L、Loli, Yen-Jen, and a cool problem

传送门
广义SAM模版题 记录一下每个点的父亲节点，每个点对应的状态节点，然后跑广义SAM，统计下数量，跳一下fail边就可以了。

#include 
using namespace std;
const int maxn = 3e5 + 150;
const int kind = 26;
typedef long long ll;
int tot1 = 1, las = 1;
int ch[maxn * 2][kind],len[maxn * 2], fa[maxn * 2];
int cnt[maxn * 2],vis[maxn],d[maxn];
inline int newn(int x) { len[++tot1] = x; return tot1; }
inline int newnq(int p, int w) {int nq = newn(len[p] + 1);int q = ch[p][w];for (int i = 0; i < kind; i++)ch[nq][i] = ch[q][i];fa[nq] = fa[q];fa[q] = nq;while (p&&ch[p][w] == q)ch[p][w] = nq, p = fa[p];return nq;
}
void sam_ins(int c) {int p = las;if (ch[p][c]) {int q = ch[p][c];if (len[q] == len[p] + 1)las = q;else las = newnq(p, c);return;}int np = newn(len[las] + 1); las = tot1;while (p && !ch[p][c])ch[p][c] = np, p = fa[p];if (!p)fa[np] = 1;else {int q = ch[p][c];if (len[q] == len[p] + 1) fa[np] = q;else {fa[np] = newnq(p, c);}}
}
int dd[maxn * 2],who[maxn * 2];
void updatecount() {for (int i = 1; i <= tot1; i++)dd[len[i]]++;for (int i = 1; i <= tot1; i++)dd[i] += dd[i - 1];for (int i = 1; i <= tot1; i++)who[dd[len[i]]--] = i;for (int i = tot1; i >= 2; i--)cnt[fa[who[i]]] += cnt[who[i]];
}
int calc(int s,int l) {while (len[fa[s]]>=l){s = fa[s];}return cnt[s];}
char s[maxn];
int main() {int n, q;scanf("%d%d", &n, &q);scanf("%s", s);for (int i = 2; i <= n; i++)scanf("%d", &vis[i]);sam_ins(s[0] - 'A');d[1] = las;cnt[las]++;vis[1] = 1;for (int i = 2; i <=n; i++) {las = d[vis[i]];sam_ins(s[i-1] - 'A');cnt[las]++;d[i] = las;}updatecount();for (int i = 0; i < q; i++) {int a, b;scanf("%d%d", &a, &b);printf("%d\n", calc(d[a], b));}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！