Pagini recente » Cod sursa (job #2397654) | Cod sursa (job #810878) | Cod sursa (job #2952908) | Cod sursa (job #810877) | Cod sursa (job #2114854)
#include <iostream>
#include <fstream>
#define nMax 103
#define cuvMax 10003
#define txtMax 1000003
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fin("ahocorasick.out");
int ord[nMax] = {};
int cindex;
char txt[txtMax];
class ahtree{
public:
char index = 0;
ahtree *v[26] = {};
ahtree *failure;
void insert(char cuv[cuvMax]);
void fix_root();
void fix();
void search();
void pre();
}*root;
void ahtree :: insert(char cuv[cuvMax]){
if(!cuv[0]){
index = cindex;
return;
}
int i = cuv[0] - 'a';
if(!v[i]){
v[i] = new ahtree;
}
v[i] ->insert(cuv + 1);
return;
}
void ahtree :: fix(){
for(int i = 0; i < 26; i ++){
if(v[i]){
if(failure ->v[i]){
v[i] ->failure = failure ->v[i];
}
else{
if(failure != root && root ->v[i]){
v[i] ->failure = root ->v[i];
}
else{
v[i] ->failure = root;
}
}
v[i] ->fix();
}
}
return;
}
void ahtree :: fix_root(){
failure = nullptr;
for(int i = 0; i < 26; i ++){
if(v[i]){
v[i] ->failure = root;
v[i] ->fix();
}
}
return;
}
void ahtree :: pre(){
if(index){
cout<<" *\n";
}
for(int i = 0; i < 26; i ++){
if(v[i]){
cout<<(char)(i + 'a')<<"("<<v[i] ->failure<<")";
v[i] -> pre();
}
}
return;
}
void ahtree :: search(){
if(index){
++ ord[index];
}
if(!txt[cindex]){
return;
}
int i = txt[cindex] - 'a';
if(v[i]){
if(failure && failure ->index){
++ ord[failure ->index];
}
++ cindex;
v[i] ->search();
}
else{
if(failure == nullptr){
++ cindex;
search();
}
else{
failure ->search();
}
}
return;
}
void search(){
ahtree *now;
int i = 0, j;
while(txt[i]){
j = txt[i] - 'a';
if(now ->v[j]){
now = now ->v[j];
++ i;
}
else{
if(now ->failure){
now = now ->failure;
}
else{
++ i;
}
}
if(now ->index){
++ ord[now ->index];
}
for(ahtree *it = now ->failure; it; it = it ->failure){
if(it ->index){
++ ord[it ->index];
}
}
}
return;
}
int main(){
int n;
char cuv[cuvMax];
root = new ahtree;
fin>>txt>>n;
for(cindex = 1; cindex <= n; cindex ++){
fin>>cuv;
root ->insert(cuv);
}
root ->fix_root();
search();
for(int i = 1; i <= n; i ++){
fout<<ord[i]<<"\n";
}
return 0;
}