首页 > 代码库 > BZOJ3172: [Tjoi2013]单词
BZOJ3172: [Tjoi2013]单词
3172: [Tjoi2013]单词
Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 1255 Solved: 568
[Submit][Status]
Description
某人读论文，一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次，现在想知道每个单词分别在论文中出现多少次。
Input
第一个一个整数N,表示有多少个单词，接下来N行每行一个单词。每个单词由小写字母组成，N<=200,单词长度不超过10^6
Output
输出N个整数，第i行的数字表示第i个单词在文章中出现了多少次。
Sample Input
3
a
aa
aaa
a
aa
aaa
Sample Output
6
3
1
3
1
题解：
SA的话直接接到一块然后二分出该串向左向右匹配的位置即可。不知道100W的SA是怎么A掉的
AC自动机的话我们直接其实就是查询有多少个节点通过fail能到达该串的结束节点，既然这样符合条件的一定bfs的时候在该点之后
那么我们按bfs逆序执行w[go[i]]+=w[i]即可。正确性显然。
又快又好写
代码：
View Code
SA的话直接接到一块然后二分出该串向左向右匹配的位置即可。不知道100W的SA是怎么A掉的
AC自动机的话我们直接其实就是查询有多少个节点通过fail能到达该串的结束节点，既然这样符合条件的一定bfs的时候在该点之后
那么我们按bfs逆序执行w[go[i]]+=w[i]即可。正确性显然。
又快又好写
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 1000000+5 26 27 #define maxm 20000000+5 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 1000000007 44 45 using namespace std; 46 47 inline int read() 48 49 { 50 51 int x=0,f=1;char ch=getchar(); 52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56 57 return x*f; 58 59 } 60 int n,m,cnt,a[maxn],w[maxn],go[maxn],t[maxn][26],p[maxn]; 61 char s[maxn]; 62 queue<int>q; 63 void bfs() 64 { 65 q.push(1); 66 while(!q.empty()) 67 { 68 int x=q.front(),y,j;q.pop(); 69 a[++cnt]=x; 70 for0(i,25) 71 { 72 j=go[x]; 73 while(j&&!t[j][i])j=go[j]; 74 if(t[x][i]) 75 { 76 go[y=t[x][i]]=j?t[j][i]:1; 77 q.push(y); 78 }else t[x][i]=j?t[j][i]:1; 79 } 80 } 81 } 82 83 int main() 84 85 { 86 87 freopen("input.txt","r",stdin); 88 89 freopen("output.txt","w",stdout); 90 91 n=read();cnt=1; 92 for1(i,n) 93 { 94 scanf("%s",s+1);m=strlen(s+1);int now=1; 95 for1(j,m) 96 { 97 int x=s[j]-‘a‘; 98 if(!t[now][x])t[now][x]=++cnt; 99 now=t[now][x];100 w[now]++;101 }102 p[i]=now;103 }104 cnt=0;105 bfs();106 for3(i,cnt,1)w[go[a[i]]]+=w[a[i]];107 for1(i,n)printf("%d\n",w[p[i]]);108 109 return 0;110 111 }
BZOJ3172: [Tjoi2013]单词
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。