fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define out(a) copy(a.begin(),a.end(),ostream_iterator<int>(cout, " "))
  5. const int M = 1e9 + 7;
  6. const int N = 17040;
  7. const int BASE = 63LL;
  8. vector<vector<pair<int, int> > > arr;
  9. ll h, p;
  10. int n, x, y, ln, cnt;
  11. int len[N], val[128], out[N];
  12. char s[N][80];
  13. ll power(ll base, int exp) {
  14. 	ll res = 1;
  15. 	while (exp) {
  16. 		if (exp & 1)
  17. 			res = (res * base) % M;
  18. 		exp >>= 1;
  19. 		base = (base * base) % M;
  20. 	}
  21.  
  22. 	return res;
  23. }
  24. ll MOD(ll x) {
  25. 	return (x % M + M) % M;
  26. }
  27. void dfs(int x, int l = 0, int sum = 0) {
  28. 	for (int i = 0; i < arr[x].size(); ++i) {
  29. 		int y = arr[x][i].first, indx = arr[x][i].second;
  30. 		out[l] = indx;
  31. 		dfs(y, l + 1, sum + len[indx]);
  32. 	}
  33. 	if (arr[x].empty() && sum >= ln) {
  34. 		ll tmp = 0;
  35. 		int k = 0, curr = 0;
  36. 		for (int i = 0; i < ln; ++i) {
  37. 			char c = s[out[curr]][k];
  38. 			tmp = ((tmp * BASE) % M + val[(int) c]) % M;
  39. 			++k;
  40. 			if (k == len[out[curr]])
  41. 				curr++, k = 0;
  42. 		}
  43. 		cnt += (tmp == h);
  44. 		int _k = 0, _curr = 0;
  45. 		for (int i = 1; i < sum - ln + 1; ++i) {
  46. 			char c = s[out[curr]][k];
  47. 			char d = s[out[_curr]][_k];
  48. 			tmp = MOD(tmp - (val[(int) d] * p) % M);
  49. 			tmp = ((tmp * BASE) % M + val[(int) c]) % M;
  50. 			cnt+=(h == tmp);
  51. 			++k;
  52. 			++_k;
  53. 			if (k == len[out[curr]])
  54. 				curr++, k = 0;
  55. 			if (_k == len[out[_curr]])
  56. 				_curr++, _k = 0;
  57.  
  58. 		}
  59. 	}
  60. }
  61. int main() {
  62. 	int id = 1;
  63. 	for (int i = 'A'; i <= 'Z'; ++i)
  64. 		val[i] = id++;
  65. 	for (int i = 'a'; i <= 'z'; ++i)
  66. 		val[i] = id++;
  67. 	for (int i = '0'; i <= '9'; ++i)
  68. 		val[i] = id++;
  69. 	scanf("%d", &n);
  70. 	arr.clear();
  71. 	arr.resize(n);
  72. 	for (int i = 0; i < n - 1; ++i) {
  73. 		scanf("%d %d %s", &x, &y, s[i]);
  74. 		len[i] = strlen(s[i]);
  75. 		arr[x].push_back(make_pair(y, i));
  76. 	}
  77. 	char t[80];
  78. 	scanf(" %s", t);
  79. 	ln = strlen(t);
  80. 	h = 0;
  81. 	for (int i = 0; i < ln; ++i)
  82. 		h = (h * BASE + val[(int) t[i]]) % M;
  83. 	p = power(BASE, ln - 1);
  84. 	dfs(0);
  85. 	printf("%d\n",cnt);
  86. 	return 0;
  87. }
  88.  
Runtime error #stdin #stdout 0s 4924KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/br8pY3
language:
C++14 (gcc 8.3)
created:
10 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!