For this Problem statement: Finding Patterns
I was implementing the Aho Corasick Algorithm based on the idea of this post. Adamant Aho Corasick
But my code is failing for two CSES test cases #12 and #14.
Could anyone please suggest where I am going wrong?
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define sz(x) x.size()
#define FOR(i,a,b) for(int i=a;i<b;++i)
const int maxN = 5e5+5,sigma = 26;
vector<int> term[maxN];
ll len[maxN],to[maxN][sigma],suffix_link[maxN],sz = 1,ans[maxN];
void add_string(string& s,int pos){
int cur = 0;
for(auto c:s){
if(!to[cur][c-'a']){
to[cur][c-'a'] = sz++;
len[to[cur][c-'a']] = len[cur]+1;
}
cur = to[cur][c-'a'];
}
term[cur].pb(pos);
}
void push_links(){
int que[sz];
int st = 0, fi = 1;
que[0] = 0;
while(st<fi){
int V = que[st++];
int U = suffix_link[V];
if(!sz(term[V]) && V != 0) for(auto x:term[U]) term[V].pb(x);
for(int c = 0;c<sigma;++c){
if(to[V][c]){
suffix_link[to[V][c]] = V?to[U][c]:0;
que[fi++] = to[V][c];
}
else{
to[V][c] = to[U][c];
}
}
}
}
void bfs(string& txt){
int idx = 0, cur = 0;
while(idx<(int)txt.length()){
if(to[cur][txt[idx]-'a']){//If transition exist from the current node through txt[idx]
cur = to[cur][txt[idx]-'a'];
++idx;
}
else if(cur){// else if there exist a suffix link but that shouldn't be root node
cur = suffix_link[cur];
// cur = to[cur][txt[idx-1]-'a'];
}
else // txt[idx] does not exist in trie
++idx;
if(sz(term[cur])) {for(auto x:term[cur]) ans[x] = 1; term[cur] = {};}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);cout.tie(NULL);
string s;cin>>s;
int q;cin>>q;
for(int i=0;i<q;++i){
string t;cin>>t;
add_string(t,i);
}
push_links();
bfs(s);
FOR(i,0,q){
if(ans[i]) cout<<"YES"<<'\n';
else cout<<"NO\n";
}
// for(int i=0;i<sz;++i){
// for(int j=0;j<26;++j)
// cout<<to[i][j]<<' ';
// cout<<'\n';
// }
// cout<<'\n';
// for(int i=0;i<sz;++i){
// if(sz(term[i])) cout<<i<<' ';
// }
// cout<<'\n';
// for(int i=0;i<sz;++i){
// cout<<suffix_link[i]<<" ";
// }
return 0;
}