Advertisement
Guest User

Untitled

a guest
Jun 19th, 2018
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.83 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. #define TASK "1"
  4.  
  5. using namespace std;
  6.  
  7. struct aho_auto {
  8.  
  9. struct node {
  10. unordered_map<int, int> to;
  11. unordered_map<int, int> go;
  12. int suff;
  13. int info;
  14. node() {
  15. info = 0;
  16. }
  17. };
  18.  
  19. vector<node> v;
  20.  
  21. aho_auto(vector<string> &ss) {
  22. v.push_back(node());
  23.  
  24. for (auto s : ss) {
  25. int h = 0;
  26. for (int i = 0; i < (int)s.size(); i++) {
  27. int c = s[i];
  28. if (v[h].to.count(c) == 0) {
  29. v.push_back(node());
  30. v[h].to[c] = v.size() - 1;
  31. }
  32. h = v[h].to[c];
  33. }
  34. v[h].info++;
  35. }
  36. queue<int> q;
  37. q.push(0);
  38. q.push(0);
  39. q.push(0);
  40. while (q.size() > 0) {
  41. int x = q.front();
  42. q.pop();
  43. int parent = q.front();
  44. q.pop();
  45. int c = q.front();
  46. q.pop();
  47. if (x == 0 || parent == 0) {
  48. v[x].suff = 0;
  49. } else {
  50. int t = v[parent].suff;
  51. while (t > 0 && v[t].to.count(c) == 0) t = v[t].suff;
  52. v[x].suff = v[t].to[c];
  53. }
  54. v[x].info += v[v[x].suff].info;
  55. for (pair<int, int> y : v[x].to) {
  56. q.push(y.second);
  57. q.push(x);
  58. q.push(y.first);
  59. }
  60. }
  61. }
  62. int size() {
  63. return v.size();
  64. }
  65. int go(int from, int c) {
  66. if (v[from].to.count(c) != 0) return v[from].to[c];
  67. if (from == 0) return 0;
  68. if (v[from].go.count(c) != 0) return v[from].go[c];
  69. int ret = go(v[from].suff, c);
  70. return v[from].go[c] = ret;
  71. }
  72. int get_info(int x) {
  73. return v[x].info;
  74. }
  75.  
  76. };
  77.  
  78. int main(){
  79. #ifdef home
  80. freopen(TASK".in","r",stdin);
  81. freopen(TASK".out","w",stdout);
  82. #endif
  83. ios::sync_with_stdio(false);
  84. int n;
  85. cin >> n;
  86. vector<string> s(n);
  87. for (int i = 0; i < n; i++) cin >> s[i];
  88. string t;
  89. cin >> t;
  90.  
  91.  
  92. auto a = aho_auto(s);
  93.  
  94. int ans = 0;
  95. int x = 0;
  96. for (int i = 0; i < (int)t.size(); i++) {
  97. x = a.go(x, t[i]);
  98. ans += a.get_info(x);
  99. }
  100. cout << ans << endl;
  101. return 0;
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement