Pagini recente » Cod sursa (job #1582299) | Cod sursa (job #2081030) | Cod sursa (job #2482385) | Cod sursa (job #2923353) | Cod sursa (job #2589299)
#include <iostream>
#include <fstream>
#include <string>
#include <unordered_map>
#include <queue>
#include <vector>
#include <chrono>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
struct nod;
nod *r;
int cv(char c){
return c-'a';
}
int fml[114];
struct nod{
nod *ch[27];
nod *suf = NULL, *dsuf = NULL;
vector<int> indices;
void add(const string &a, int index){
nod *p = this;
for(auto c : a){
int ci = cv(c);
if(p->ch[ci] == NULL){
p->ch[ci] = new nod();
}
p = p->ch[ci];
}
p->indices.push_back(index);
}
void upgrade(){
queue<nod*> qu;
qu.push(this);
while(!qu.empty()){
nod *p = qu.front();
qu.pop();
for(int ci = 0; ci < 26; ++ci){
nod *q = p->ch[ci];
if(q != NULL){
q->suf = p->suf;
while(q->suf != NULL && q->suf->ch[ci] == NULL){
q->suf = q->suf->suf;
}
if(q->suf == NULL){
q->suf = r;
}else{
q->suf = q->suf->ch[ci];
}
qu.push(q);
}
}
}
}
void upgrade2(){
queue<nod*> qu;
qu.push(this);
while(!qu.empty()){
nod *p = qu.front();
qu.pop();
for(int ci = 0; ci < 26; ++ci){
nod *q = p->ch[ci];
if(q != NULL){
q->dsuf = p->dsuf;
while(q->dsuf != NULL && q->dsuf->indices.empty()){
q->dsuf = q->dsuf->suf;
}
qu.push(q);
}
}
}
}
nod *next(char c){
int ci = cv(c);
nod *p = this;
while(p->suf != NULL && p->ch[ci] == NULL){
p = p->suf;
}
if(p->ch[ci] == NULL){
return r;
}else{
return p->ch[ci];
}
}
void addme(){
if(!indices.empty()){
fml[indices.front()]++;
}
}
void stupid(){
queue<nod*> qu;
qu.push(this);
while(!qu.empty()){
nod *p = qu.front();
qu.pop();
for(int ci = 0; ci < 26; ++ci){
nod *q = p->ch[ci];
if(q != NULL){
for(int i = 1; i < q->indices.size(); ++i){
fml[q->indices[i]] = fml[q->indices.front()];
}
qu.push(q);
}
}
}
}
};
int n;
string s, a;
void read(){
r = new nod();
fin >> s >> n;
for(int i = 1; i <= n; ++i){
fin >> a;
r->add(a, i);
}
}
void solve(){
r->upgrade();
r->upgrade2();
nod *p = r;
for(auto c : s){
p = p->next(c);
nod *q = p;
while(q != NULL){
q->addme();
q = q->dsuf;
}
}
r->stupid();
}
void write(){
for(int i = 1; i <= n; ++i){
fout << fml[i] << "\n";
}
}
int main(){
// ios_base::sync_with_stdio(false);
read();
solve();
write();
return 0;
}