Counting Words

input/code.cpp: In function 'int main()':
input/code.cpp:55:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<s.g.size();++i){
                         ^
input/code.cpp:71:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(;i<a.size();++i){
                 ^
input/code.cpp:75:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i<a.size())cout<<"0\n";
               ^

#include <bits/stdc++.h>
using namespace std;
struct SuffixAutomaton{
	vector<map<char,int>> g;
	vector<int> link,len;
	int last;
	void addC(char c){
		int p=last;int t=link.size();
		link.push_back(0);
		len.push_back(len[last]+1);
		g.push_back(map<char,int>());
		while(p!=-1&&g[p].count(c)==0){
			g[p][c]=t;p=link[p];
		}
		if(p!=-1){
			int q=g[p][c];
			if(len[p]+1==len[q])link[t]=q;
			else{
				int qq=link.size();
				link.push_back(link[q]);
				len.push_back(len[p]+1);
				g.push_back(g[q]);
				while(p!=-1&&g[p][c]==q){
					g[p][c]=qq;p=link[p];
				}
				link[q]=qq;link[t]=qq;
			}
		}
		last=t;
	}
	SuffixAutomaton() : SuffixAutomaton(""){}
	SuffixAutomaton(string s){
		last=0;
		g.push_back(map<char,int>());
		link.push_back(-1);
		len.push_back(0);
		for(auto& it : s)addC(it);
	}
	vector<int> terminals(){
		vector<int> t;int p=last;
		while(p>0){t.push_back(p);p=link[p];}
		return t;
	}
};

int main(){
	string a;
	cin>>a;
	SuffixAutomaton s(a);
	vector<vector<int>> edges(s.g.size());
	vector<int> incount(s.g.size());
	vector<int> q(s.g.size());
	vector<int> dp(s.g.size());
	int nq=0,qi=0;
	for(int i=0;i<s.g.size();++i){
		for(auto& it : s.g[i])incount[i]++,edges[it.second].push_back(i);
		if(!incount[i])q[nq++]=i;
	}
	for(const auto& it : s.terminals())++dp[it];
	while(qi<nq){
		int i=q[qi++];
		for(auto& it : s.g[i])dp[i]+=dp[it.second];
		for(auto& it : edges[i])if(!--incount[it])q[nq++]=it;
	}
	int n;
	cin>>n;
	while(n--){
		cin>>a;
		int p = 0;
		int i = 0;
		for(;i<a.size();++i){
			if(s.g[p].count(a[i]))p=s.g[p][a[i]];
			else break;
		}
		if(i<a.size())cout<<"0\n";
		else cout<<dp[p]<<'\n';
	}
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED