Guest User

Untitled

a guest
Aug 22nd, 2015
284
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.20 KB | None | 0 0
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <vector>
  4. #include <cstring>
  5.  
  6. using namespace std;
  7.  
  8. //Axo-Korasik
  9. const int alphabet = 95;
  10. struct item{
  11.     int next[alphabet];
  12.     bool leaf;
  13.     int suffix_link;
  14.     int p;
  15.     char pch;
  16.     int go[alphabet];
  17.     int terminal;
  18.     item(){
  19.         for (int i=0; i<alphabet; i++){
  20.             next[i] = go[i] = -1;
  21.         }
  22.         leaf = false;
  23.         suffix_link = p = -1;
  24.         terminal = -1;
  25.     }
  26. };
  27. vector <item> trie;
  28. void init_trie(){
  29.     trie.push_back(item());
  30. }
  31. void add_string(char* s){
  32.     int v = 0, n = strlen(s);
  33.     for (int i=0; i<n; i++){
  34.         int ch = int(s[i]) - 32;
  35.         int prev = v;
  36.         if (trie[v].next[ch] != -1){
  37.             v = trie[v].next[ch];
  38.         }
  39.         else{
  40.             trie[v].next[ch] = trie.size();
  41.             trie.push_back(item());
  42.             v = trie[v].next[ch];
  43.         }
  44.         trie[v].p = prev;
  45.         trie[v].pch = s[i];
  46.     }
  47.     trie[v].leaf = true;
  48.     trie[v].terminal = true;
  49. }
  50. int go(int v, char pch);
  51. int get_link(int v){
  52.     if (trie[v].suffix_link == -1){
  53.         if (!v || !trie[v].p) trie[v].suffix_link = 0;
  54.         else trie[v].suffix_link = go(get_link(trie[v].p), trie[v].pch);
  55.     }
  56.     return trie[v].suffix_link;
  57. }
  58. int go(int v, char pch){
  59.     if (trie[v].go[int(pch)-32] == -1){
  60.         if (trie[v].next[int(pch)-32] != -1) trie[v].go[int(pch)-32] = trie[v].next[int(pch)-32];
  61.         else trie[v].go[int(pch) - 32] = (v != 0 ? go(get_link(v), pch) : 0);
  62.     }
  63.     return trie[v].go[int(pch)-32];
  64. }
  65. //
  66. bool go_to_the_next_suffix_link(int v){
  67.     if (v == 0) return false;
  68.     if (trie[v].terminal == 1) return true;
  69.     if (trie[v].terminal == 0) return false;
  70.     return trie[v].terminal = go_to_the_next_suffix_link(get_link(v));
  71. }
  72. bool move(char* text, int len){
  73.     int v = 0;
  74.     for (int i=0; i<len; i++){
  75.         v = go(v, text[i]);
  76.         if (go_to_the_next_suffix_link(v)) return true;
  77.     }
  78.     return false;
  79. }
  80. void solution(){
  81.     init_trie();
  82.     int n;
  83.     scanf("%d",&n);
  84.     getchar();
  85.     char pattern[80000+5];
  86.     for (int i=0; i<n; i++){
  87.         gets(pattern);
  88.         add_string(pattern);
  89.     }
  90.     int sz = trie.size();
  91.     char text[1000000+5];
  92.     int len;
  93.     while (gets(text)){
  94.         len = strlen(text);
  95.         if (len == 0) continue;
  96.         if (move(text,len)){
  97.             puts(text);
  98.         }
  99.     }
  100. }
  101. int main(){
  102.     freopen("input.txt","r",stdin);
  103.     freopen("output.txt","w",stdout);
  104.     solution();
  105.     return 0;
  106. }
Advertisement
Add Comment
Please, Sign In to add comment