Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <stdio.h>
- #include <vector>
- #include <cstring>
- using namespace std;
- //Axo-Korasik
- const int alphabet = 95;
- struct item{
- int next[alphabet];
- bool leaf;
- int suffix_link;
- int p;
- char pch;
- int go[alphabet];
- int terminal;
- item(){
- for (int i=0; i<alphabet; i++){
- next[i] = go[i] = -1;
- }
- leaf = false;
- suffix_link = p = -1;
- terminal = -1;
- }
- };
- vector <item> trie;
- void init_trie(){
- trie.push_back(item());
- }
- void add_string(char* s){
- int v = 0, n = strlen(s);
- for (int i=0; i<n; i++){
- int ch = int(s[i]) - 32;
- int prev = v;
- if (trie[v].next[ch] != -1){
- v = trie[v].next[ch];
- }
- else{
- trie[v].next[ch] = trie.size();
- trie.push_back(item());
- v = trie[v].next[ch];
- }
- trie[v].p = prev;
- trie[v].pch = s[i];
- }
- trie[v].leaf = true;
- trie[v].terminal = true;
- }
- int go(int v, char pch);
- int get_link(int v){
- if (trie[v].suffix_link == -1){
- if (!v || !trie[v].p) trie[v].suffix_link = 0;
- else trie[v].suffix_link = go(get_link(trie[v].p), trie[v].pch);
- }
- return trie[v].suffix_link;
- }
- int go(int v, char pch){
- if (trie[v].go[int(pch)-32] == -1){
- if (trie[v].next[int(pch)-32] != -1) trie[v].go[int(pch)-32] = trie[v].next[int(pch)-32];
- else trie[v].go[int(pch) - 32] = (v != 0 ? go(get_link(v), pch) : 0);
- }
- return trie[v].go[int(pch)-32];
- }
- //
- bool go_to_the_next_suffix_link(int v){
- if (v == 0) return false;
- if (trie[v].terminal == 1) return true;
- if (trie[v].terminal == 0) return false;
- return trie[v].terminal = go_to_the_next_suffix_link(get_link(v));
- }
- bool move(char* text, int len){
- int v = 0;
- for (int i=0; i<len; i++){
- v = go(v, text[i]);
- if (go_to_the_next_suffix_link(v)) return true;
- }
- return false;
- }
- void solution(){
- init_trie();
- int n;
- scanf("%d",&n);
- getchar();
- char pattern[80000+5];
- for (int i=0; i<n; i++){
- gets(pattern);
- add_string(pattern);
- }
- int sz = trie.size();
- char text[1000000+5];
- int len;
- while (gets(text)){
- len = strlen(text);
- if (len == 0) continue;
- if (move(text,len)){
- puts(text);
- }
- }
- }
- int main(){
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- solution();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment