济宁互联网推广公司,南通网站推广优化费用,河南焦作有做网站开发的公司吗,软件开发学什么传送门 Description 某人读论文#xff0c;一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次#xff0c;现在想知道每个单词分别在论文中出现多少次。 Input 第一个一个整数N,表示有多少个单词#xff0c;接下来N行每行一个单词。每个单词由小写字母组成一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次现在想知道每个单词分别在论文中出现多少次。 Input 第一个一个整数N,表示有多少个单词接下来N行每行一个单词。每个单词由小写字母组成N200,单词长度不超过10^6 Output 输出N个整数第i行的数字表示第i个单词在文章中出现了多少次。 Sample Input 3 a aa aaa Sample Output 6 3 1 哎这不是多字符串的问题吗我们首先就想到了AC自动机 fail指针的意义是什么呢就是一个后缀链接而后缀是覆盖了所有的子串的所以我们可以用一次树DP就统计出了每一个单词出现的次数。 /**************************************************************Problem: 3172User: geng4512Language: CResult: AcceptedTime:256 msMemory:237132 kb
****************************************************************/#includecstdio
#define MAXN 2000000
#define MAXC 26
int a[MAXN][MAXC], pre[MAXN], sz 1, q[MAXN], cnt[MAXN], ed[MAXN], n;
char s[MAXN];
inline int Insert(char *s) {int c, p 1;for(int i 0; s[i]; i) {c s[i] - a;if(!a[p][c]) a[p][c] sz;p a[p][c]; cnt[p];}return p;
}
void Build() {int l 1, r 0;for(int i 0; i MAXC; i)if(!a[1][i]) a[1][i] 1;else {pre[a[1][i]] 1;q[ r] a[1][i];}while(l r) {int u q[l ];for(int i 0; i MAXC; i)if(!a[u][i]) a[u][i] a[pre[u]][i];else {pre[a[u][i]] a[pre[u]][i];q[ r] a[u][i];}}for(int i r; i; -- i) cnt[pre[q[i]]] cnt[q[i]];
}
int main() {scanf(%d, n);for(int i 1; i n; i) {scanf(%s, s);ed[i] Insert(s);}Build();for(int i 1; i n; i) printf(%d\n, cnt[ed[i]]);return 0;
} 转载于:https://www.cnblogs.com/geng4512/p/5296869.html
