Pagini recente » Cod sursa (job #1083205) | Cod sursa (job #84639) | Cod sursa (job #1301677) | Cod sursa (job #35196) | Cod sursa (job #3299566)
#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
string numeFisier="ahocorasick";
ifstream fin(numeFisier+".in"); ofstream fout(numeFisier+".out");
#define cin fin
#define cout fout
#define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
//#define int ll
int t, n, m, k, a[300010], q, l, r;
string text;
string pattern[101];
int occurrences[101];
class AhoCorasickAutomaton{
public:
class Vertex{
public:
Vertex* suffLink=nullptr;
Vertex* pchr[26];
vector<int> wordIndexes;
int lazy=0;
int inDegree = 0;
};
// set<Vertex*> s;
// map<Vertex*, int> h;
Vertex *root = new Vertex();
Vertex * node;
void addWordTrie(Vertex* Root,string s, int index){
Vertex* node = Root;
for(int i=0; i<s.length(); i++){
auto parent = node;
if( !node->pchr[ s[i] - 'a' ] ){
node->pchr[ s[i] - 'a' ] = new Vertex();
node->pchr[ s[i]-'a' ]->suffLink=root;
}
node = node->pchr[ s[i]-'a' ];
}
node->wordIndexes.pb(index);
}
stack<Vertex*> st;
void makeSuffixLinks(){
// int sz = s.size();
// s.insert(root);
// if(s.size()>sz){
// h[root] = s.size();
// }
queue<Vertex*> q;
q.push(root);
while(!q.empty()){
auto f = q.front();
q.pop();
for(char c='a' ;c<='z'; c++){
if(!f->pchr[c-'a'])continue;
node = f->pchr[c-'a'];
if(f!=root){
node->suffLink = f->suffLink;
while( !node->suffLink->pchr[ c - 'a' ] && (node->suffLink->suffLink != node->suffLink) ){
node->suffLink = node->suffLink->suffLink;
}
if( node->suffLink->pchr[ c-'a' ] ){
node->suffLink = node->suffLink->pchr[ c-'a' ];
}
node->suffLink->inDegree++;
}
q.push(node);
st.push(node);
}
}
}
void propagateLazy(){
while(!st.empty()){
auto f = st.top();
st.pop();
if(f->inDegree!=0){
cout<<f->inDegree<<"-\n";
exit(0);
}
//cout<<f<<"h\n";
f->suffLink->lazy+=f->lazy;
f->suffLink->inDegree--;
for(auto index:f->wordIndexes){
occurrences[index]+=f->lazy;
}
f->lazy=0;
}
}
void searchText(string &text, int occurrences[]){
Vertex* node = root;
for(int i=0; i<text.length(); i++){
char c = text[i];
if( node->pchr[ c-'a' ] ){
node = node->pchr[ c-'a' ];
}
else{
while( !node->pchr[ c - 'a' ] && node->suffLink!=node ){
node = node->suffLink;
}
if(node->pchr[ c-'a' ]){
node = node->pchr[c-'a'];
}
}
node->lazy++;
//cout<<"+"<<node<<"\n";
}
propagateLazy();
}
} ahoCorasick;
int32_t main(){
INIT
cin>>text;
cin>>k;
for(int i=1; i<=k; i++){
cin>>pattern[i];
}
ahoCorasick.root->suffLink = ahoCorasick.root;
for(int i=1; i<=k; i++){
ahoCorasick.addWordTrie(ahoCorasick.root, pattern[i], i);
}
ahoCorasick.makeSuffixLinks();
ahoCorasick.searchText(text, occurrences);
for(int i=1; i<=k; i++){
cout<<occurrences[i]<<"\n";
}
return 0;
}