Cod sursa(job #1652125)

Utilizator vladttturcuman vlad vladtt Data 14 martie 2016 18:03:45
Problema Aho-Corasick Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 2.36 kb
#include <fstream>
#include <iostream>
#include <string>
#include <map>


#define M_MAX 110
#define STR_Max_Length 1000100
#define WORDS_Max_Length 10100
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");

string str;

map<std::string,int> trie;
map<string,string> best;
string dictionary[M_MAX];

int m;

void create_ReverseWay()
{
    // insert all words from dictionary in trie

    for(int i=1;i<=m;i++)
    {
        int n=dictionary[i].length()-1;

        std::string word="";
        word+=dictionary[i][0];
        trie[word]=1;

        for(int y=1; y<=n;y++)
        {
            word+=dictionary[i][y];
            trie[word]=1;
        }
    }

    // calculate best reverse for each word

    for(int i=1;i<=m;i++)
    {
        int n=dictionary[i].length()-1;

        // cout<<"BEST -> " << word<<' '<<best[word]<<'\n';

        string word="";
        word+=dictionary[i][0];

        best[word]="";

        for(int y=1; y<=n;y++)
        {
            word+=dictionary[i][y];

            if(best.find(word)==best.end())
            {
                string tmp="";

                for(int j=y;j>=1;j--)
                {
                    tmp = word[j] + tmp;

                    if(trie[tmp]!=0)
                        best[word]=tmp;
                }
            }

           // cout<<"BEST -> " << word<<' '<<best[word]<<'\n';

        }


    }

}

void verif(string &ck,string k,char a)
{
    while(ck!=a+"")
    {
        if(trie[ck]!=0)
            return;

        k=best[k];
        ck=k+a;
    }
    if(trie[ck]==0)
        ck="";
}

void solve()
{
   create_ReverseWay();

    string nod="";
    string ck="";
    string k="";

    int n=str.length()-1;

    for(int i=0;i<=n;i++)
    {
        ck=k;

        ck+=str[i];

        verif(ck,k,str[i]);

        k=ck;

        while(ck!="")
        {
           // cout<<ck<<'\n';
            trie[ck]=trie[ck]+1;
            ck=best[ck];
        }
    }

}

void read()
{
    getline(fin,str);
    fin>>m; fin.get();
    for(int i=1;i<=m;i++)
        getline(fin,dictionary[i]);
}

void write()
{
    for(int i=1;i<=m;i++)
        fout<<trie[dictionary[i]]-1<<'\n';
}

int main()
{

    read();

    solve();

    write();

    return 0;
}