Cod sursa(job #2137242)

Utilizator vladttturcuman vlad vladtt Data 20 februarie 2018 18:02:13
Problema Aho-Corasick Scor 95
Compilator cpp Status done
Runda Arhiva educationala Marime 2.19 kb

//#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <cstring>

#define NMax 101
using namespace std;
ifstream cin("ahocorasick.in");
ofstream cout("ahocorasick.out");

string word[NMax];

struct Node{
    Node * next[26];
    Node * go[26];
    
    Node * link;
    Node * dad;
    
    char lastChar;
    int occ;
    
    Node(Node * _dad, char _lastChar){
        dad = _dad,
        lastChar = _lastChar,
        link = NULL,
        memset(next,0,sizeof(next)),
        memset(go, 0 ,sizeof(go)), occ = 0;
    }
} * Root;

void Add(string s){
    Node * node = Root;
    for(auto it : s){
        if(!node->next[it-'a']) node->next[it-'a'] = new Node(node, it);
        node = node->next[it-'a'];
    }
}

Node * GetLink(Node * node);

Node * go(Node * node, char c){
    if(node->go[c-'a']) return node->go[c-'a'];
    if(node->next[c-'a']) return node->go[c-'a'] = node->next[c-'a'];
    if(node == Root) return node->go[c-'a'] = Root;
    return node->go[c-'a'] = go(GetLink(node),c);
}

Node * GetLink(Node * node){
    if(node->link) return node->link;
    if(node == Root || node->dad == Root) return node->link = Root;
    return node->link = go(GetLink(node->dad), node->lastChar);
}

void LinkDfs(Node * node){
    GetLink(node);
    for(int i = 0;i<26;i++)
        if(node->next[i]) LinkDfs(node->next[i]);
}

void Propagate(){
    vector<Node*> que;
    que.push_back(Root);
    int act = 0;
    while(act < que.size()){
        for(int i = 0;i<26;i++)
            if(que[act]->next[i]) que.push_back(que[act]->next[i]);
        act++;
    }
    for(int i = que.size()-1;i>=0;i--)
        que[i]->link->occ += que[i]->occ;
}

int Get(string s){
    Node * node = Root;
    for(auto it:s)
        node = node->next[it-'a'];
    return node->occ;
}

int main() {
  
    Root = new Node(NULL, NULL);
    string str;
    int n;
    cin>>str;
    
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>word[i];
        Add(word[i]);
    }
    
    LinkDfs(Root);
    
    Node * node = Root;
    for(auto it : str){
        node = go(node, it);
        node->occ++;
    }
    
    Propagate();
    
    for(int i=1;i<=n;i++)
        cout<<Get(word[i])<<'\n';

    return 0;
}