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. 		char ccc;//line to read the newline
  47. 		scanf("%c", &ccc);
  48.  
  49. 		for(i=0;i<n;i=i+1){
  50. 			ans[i]=0;
  51. 			scanf("%c %lld\n", &ta[i],&tp[i]);
  52. 			//cin>>ta[i]>>tp[i];
  53. 			tp[i]--;
  54. 			//cout<<t[i].p<<endl;
  55. 			if(tp[i]>=0)
  56. 				leaf.reset(tp[i]);
  57. 			//cout<<i<<endl;
  58. 		}
  59. 		//DFS Path
  60. 		for(i=0;i<n;i++){
  61. 			if(leaf[i]){
  62. 				//cout<<"Leaf "<<i<<endl;
  63. 				len=0,j=i;
  64. 				while(j!=-1){
  65. 				cmpn[len]=j;
  66. 				cmp[len++]=ta[j];
  67. 				j=tp[j];
  68. 				}
  69. 				//cout<<"DFS String "<<cmp<<endl;
  70. 				//Pre-Process
  71. 					ll i=0,j=-1;
  72. 					b[0]=-1;
  73. 					while(i<l){
  74. 						while(j>=0 && s[i]!=s[j]) j=b[j];
  75. 						i++;j++;b[i]=j;
  76. 					}
  77. 					//Search
  78. 					i=0,j=0;
  79. 					while(i<len){
  80. 						while (j>=0 && cmp[i]!=s[j]) j=b[j];
  81. 						i++;j++;
  82. 						if (j==l && nodes[cmpn[i-j]]){
  83. 							for(k=len-1;k>=i-j;k--)
  84. 							ans[cmpn[k]]+=1;
  85. 							nodes[cmpn[i-j]]=false;
  86. 							j=b[j];
  87. 						}
  88. 					}
  89.  
  90. 			}
  91. 		}
  92.  
  93. 		//Answer
  94. 		for(i=0;i<n;i++)
  95. 			printf("%lld ",ans[i]);
  96. 		printf("\n");
  97. 	}
  98. 	return 0;
  99. }
Success #stdin #stdout 0s 19376KB
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 
4 4 4 3 3 2 2 1 1 1 
10 9 8 7 6 5 4 3 2 1
https://ideone.com/ePBE8n
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!