Pagini recente » Cod sursa (job #618858) | Cod sursa (job #2859841) | Cod sursa (job #1342786) | Cod sursa (job #3190171) | Cod sursa (job #782563)
Cod sursa(job #782563)
#include <fstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <vector>
using namespace std;
int N;
string A, B[102];
map<string, string> M;
map<string, vector<string> > R;
map<string, int> P;
void Dfs(string now)
{
for (vector<string>::iterator it = R[now].begin(); it != R[now].end(); ++it)
{
Dfs(*it);
P[now] += P[*it];
}
}
int main()
{
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
fin >> A >> N;
M[string()] = string();
for (int i = 1; i <= N; ++i)
{
fin >> B[i];
string now;
for (size_t j = 0; j < B[i].size(); ++j)
{
now += B[i][j];
if (M.find(now) == M.end())
M[now] = string();
}
}
for (map<string, string>::iterator it = M.begin(); it != M.end(); ++it)
{
for (int i = 0; i < 26; ++i)
if (M.find(it->first + char(i + 'a')) != M.end())
{
string aux = it->second;
while (aux != string() && M.find(aux + char(i + 'a')) == M.end())
aux = M[aux];
if (it->first != aux && M.find(aux + char(i + 'a')) != M.end())
{
M[it->first + char(i + 'a')] = aux + char(i + 'a');
R[aux + char(i + 'a')].push_back(it->first + char(i + 'a'));
}
else
{
M[it->first + char(i + 'a')] = aux;
R[aux].push_back(it->first + char(i + 'a'));
}
}
}
string now;
for (size_t i = 0; i < A.size(); ++i)
{
while (now != string() && M.find(now + A[i]) == M.end())
now = M[now];
if (M.find(now + A[i]) != M.end())
{
++P[now + A[i]];
now += A[i];
}
}
Dfs(string());
for (int i = 1; i <= N; ++i)
fout << P[B[i]] << '\n';
fin.close();
fout.close();
}