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,l,ans[100001],j,k;
  27. 	ll i;
  28. 	ll len,cmpn[100001],b[100001];
  29. 	char s[100001],cmp[100001];
  30. 	ll n,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.  
  44. 		for(i=0;i<n;i=i+1){
  45. 			//scanf("%c %lld",&ta[i],&tp[i]);
  46. 			cin>>ta[i]>>tp[i];
  47. 			tp[i]--;
  48.  
  49. 			ans[i]=0;
  50. 			if(tp[i]>=0)
  51. 				leaf.reset(tp[i]);	
  52. 		}
  53.  
  54. 		//DFS Path
  55. 		for(i=0;i<n;i++){
  56. 			if(leaf[i]){
  57. 				len=0,j=i;
  58. 				while(j!=-1){
  59. 				cmpn[len]=j;
  60. 				cmp[len++]=ta[j];
  61. 				j=tp[j];
  62. 				}
  63. 				//cout<<"DFS String "<<cmp<<endl;
  64. 				//Pre-Process
  65. 					ll i=0,j=-1;
  66. 					b[0]=-1;
  67. 					while(i<l){
  68. 						while(j>=0 && s[i]!=s[j]) j=b[j];
  69. 						i++;j++;b[i]=j;
  70. 					}
  71. 					//Search
  72. 					i=0,j=0;
  73. 					while(i<len){
  74. 						while (j>=0 && cmp[i]!=s[j]) j=b[j];
  75. 						i++;j++;
  76. 						if (j==l && nodes[cmpn[i-j]]){
  77. 							for(k=len-1;k>=i-j;k--)
  78. 							ans[cmpn[k]]+=1;
  79. 							nodes[cmpn[i-j]]=false;
  80. 							j=b[j];
  81. 						}
  82. 					}
  83. 			}
  84. 		}
  85.  
  86. 		//Answer
  87. 		for(i=0;i<n;i++)
  88. 			printf("%lld ",ans[i]);
  89. 		printf("\n");
  90. 	}
  91. 	return 0;
  92. }
  93.  
Success #stdin #stdout 0s 19368KB
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/By0PQu
language:
C++14 (gcc 8.3)
created:
7 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!