Pagini recente » Cod sursa (job #2355556) | Cod sursa (job #159083) | Cod sursa (job #573267) | Cod sursa (job #393705) | Cod sursa (job #1652125)
#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;
}