fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4. #include <bitset>
  5. #include <fstream>
  6. #include <string.h>
  7. #include <list>
  8. #include <math.h>
  9. #include <algorithm>
  10. #include <bits/stdc++.h>
  11. using namespace std;
  12.  
  13. typedef vector<int> vi;
  14. typedef pair<int,int> ii;
  15. typedef vector<ii> vii;
  16.  
  17. typedef unsigned int ui;
  18. typedef unsigned long long llu;
  19. typedef unsigned long lu;
  20. typedef long long ll;
  21. #define MAX_N 100010
  22.  
  23. //----------------------------------------------------
  24.  
  25. int main(){
  26. 	ll test,n,l,ans[100001],j,k;
  27. 	ll i;
  28. 	ll len,cmpn[100001],b[100001];
  29. 	char s[100001],cmp[100001];
  30. 	ll tp[100010];
  31. 	char ta[100010];
  32. 	bitset<100001> leaf,nodes;
  33.  
  34. 	scanf("%lld",&test);
  35. 	while(test--){
  36. 		//Input
  37. 		leaf.set();
  38. 		nodes.set();
  39. 		scanf("%lld %lld",&n,&l);
  40. 		scanf("%s",s);
  41. 		for (i=0; i<l/2; i++)
  42. 		    swap(s[i], s[l-i-1]);
  43. 		//cout<<"Reverse String:"<<s<<endl;
  44. 		//cout<<n<<l;
  45.  
  46.  
  47. 		for(i=0;i<n;i=i+1){
  48. 			ans[i]=0;
  49. 			scanf("%c %lld",&ta[i],&tp[i]);
  50. 			//cin>>ta[i]>>tp[i];
  51. 			tp[i]--;
  52. 			//cout<<t[i].p<<endl;
  53. 			if(tp[i]>=0)
  54. 				leaf.reset(tp[i]);
  55. 			//cout<<i<<endl;
  56. 		}
  57.  
  58. 		//DFS Path
  59. 		for(i=0;i<n;i++){
  60. 			if(leaf[i]){
  61. 				//cout<<"Leaf "<<i<<endl;
  62. 				len=0,j=i;
  63. 				while(j!=-1){
  64. 				cmpn[len]=j;
  65. 				cmp[len++]=ta[j];
  66. 				j=tp[j];
  67. 				}
  68. 				//cout<<"DFS String "<<cmp<<endl;
  69. 				//Pre-Process
  70. 					ll i=0,j=-1;
  71. 					b[0]=-1;
  72. 					while(i<l){
  73. 						while(j>=0 && s[i]!=s[j]) j=b[j];
  74. 						i++;j++;b[i]=j;
  75. 					}
  76. 					//Search
  77. 					i=0,j=0;
  78. 					while(i<len){
  79. 						while (j>=0 && cmp[i]!=s[j]) j=b[j];
  80. 						i++;j++;
  81. 						if (j==l && nodes[cmpn[i-j]]){
  82. 							for(k=len-1;k>=i-j;k--)
  83. 							ans[cmpn[k]]+=1;
  84. 							nodes[cmpn[i-j]]=false;
  85. 							j=b[j];
  86. 						}
  87. 					}
  88.  
  89. 			}
  90. 		}
  91.  
  92. 		//Answer
  93. 		for(i=0;i<n;i++)
  94. 			printf("%lld ",ans[i]);
  95. 		printf("\n");
  96. 	}
  97. 	return 0;
  98. }
Runtime error #stdin #stdout 0s 18552KB
comments (?)
stdin
copy 
2
10 2
sm
s 0
s 1
m 2
s 3
m 4
s 5
m 6
m 7
s 8
m 9
10 1
y
y 0
y 1
y 2
y 3
y 4
y 5
y 6
y 7
y 8
y 9
stdout
copy 
Standard output is empty
https://ideone.com/3DEx7V
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!