fork download
  1. #include <iostream>
  2. #include <queue>
  3. #include <string>
  4. using namespace std;
  5.  
  6. struct Trie {
  7. bool output;
  8. Trie* go[96], *fail;
  9.  
  10. ~Trie() {
  11. for(int i=0; i<96; i++) if (go[i]) delete go[i];
  12. }
  13.  
  14. void insert(char* s) {
  15. if (*s == '\0') {
  16. output = true;
  17. return;
  18. }
  19.  
  20. int n = *s - 32;
  21. if (!go[n]) go[n] = new Trie();
  22. go[n]->insert(s+1);
  23. }
  24. };
  25.  
  26. void BFS(Trie* root) {
  27. queue<Trie*> Q;
  28. root->fail = root; Q.push(root);
  29. while (!Q.empty()) {
  30. Trie* cur = Q.front(); Q.pop();
  31. for(int i=0; i<96; i++) {
  32. Trie* next = cur->go[i];
  33. if (!next) continue;
  34.  
  35. if (cur == root) next->fail = root;
  36. else {
  37. Trie* dest = cur->fail;
  38. while (dest != root && !dest->go[i])
  39. dest = dest->fail;
  40. if (dest->go[i]) dest = dest->go[i];
  41. next->fail = dest;
  42. }
  43.  
  44. if (next->fail->output) next->output = true;
  45. Q.push(next);
  46. }
  47. }
  48. }
  49.  
  50. int find(string s, Trie* root) {
  51. int ret = 0;
  52. Trie* cur = root;
  53. for(int i=0; s[i]; i++) {
  54. int n = s[i] - 32;
  55. while (cur != root && !cur->go[n])
  56. cur = cur->fail;
  57. if (cur->go[n]) cur = cur->go[n];
  58.  
  59. if (cur->output) {
  60. ++ret;
  61. cur = root;
  62. }
  63. }
  64. return ret;
  65. }
  66.  
  67. int main()
  68. {
  69. ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  70. int N, M; char str[81];
  71.  
  72. while (true) {
  73. cin >> N >> M;
  74. if (N == 0) break;
  75.  
  76. Trie* root = new Trie();
  77. while (N--) {
  78. cin >> str;
  79. root->insert(str);
  80. }
  81. BFS(root);
  82.  
  83. string S; getline(cin, S);
  84. int ans = 0;
  85. while (M--) {
  86. getline(cin ,S);
  87. ans += find(S, root);
  88. }
  89. cout << ans << "\n";
  90.  
  91. delete root;
  92. }
  93. }
Success #stdin #stdout 0s 5656KB
stdin
4 6
:-)
:-(
(-:
)-:
Hello uncle John! :-) :-D
I am sad or happy? (-:-(?
I feel so happy, my head spins
(-:-)(-:-)(-:-)(-:-) :-) (-: :-)
but then sadness comes :-(
Loves you, Joanna :-)))))
3 1
:)
):
))
:):)):)):)):(:((:(((:):)
0 0
stdout
11
8