Counting Words

input/code.cpp: In function 'int main()':
input/code.cpp:57:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < t.size(); ++i) {
                              ^
input/code.cpp:77:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < t.size(); ++i) {
                              ^

#include <bits/stdc++.h>
using namespace std;
vector<int> suffixArray(string s, int S = 256) {
	int n=s.size();int N=n+S;
	vector<int> sa(n), ra(n);
	for(int i=0;i<n;i++) {sa[i]=i;ra[i]=s[i];}
	for(int k=0;k<n;k?k*=2:k++) {
		vector<int> nsa(sa), nra(n), cnt(N);
		for(int i=0;i<n;i++) nsa[i]=(nsa[i]-k+n)%n;
		for(int i=0;i<n;i++) cnt[ra[i]]++;
		for(int i=1;i<N;i++) cnt[i]+=cnt[i-1];
		for(int i=n-1;i>=0;i--) sa[--cnt[ra[nsa[i]]]]=nsa[i];
		int r=0;
		for(int i=1;i<n;i++) {
			if(ra[sa[i]]!=ra[sa[i-1]]) r++;
			else if(ra[(sa[i]+k)%n]!=ra[(sa[i-1]+k)%n]) r++;
			nra[sa[i]]=r;
		}
		ra=nra;
	}
	return sa;
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	string s;
	cin>>s;
	int m;
	cin>>m;
	s.push_back(0);
	vector<int> sa = suffixArray(s);
	auto s2 = s;
	s2.pop_back();
	s2.push_back(127);
	vector<int> sa2 = suffixArray(s2);
	/*
	cout<<'\n';
	for(int i = 0; i < sa.size(); ++i) {
		cout<<sa[i]<<' ';
	}
	cout<<'\n';
	for(int i = 0; i < sa2.size(); ++i) {
		cout<<sa2[i]<<' ';
	}
	cout<<'\n';
	*/
	int n = s.size();
	for(int i = 0; i < m; ++i) {
		string t;
		cin>>t;
		int lo = 0;
		int hi = n-1; 
		int best = n; 
		//lower_bound
		while(lo <= hi) {
			int mid = (lo+hi)/2;
			for(int i = 0; i < t.size(); ++i) {
				if(t[i] < s[sa[mid]+i]) {
					break;
				}
				if(t[i] > s[sa[mid]+i]) {
					goto ohi;
				}
			}
			best = mid;
			hi = mid-1;
			continue;
			ohi:;
			lo = mid+1;
		}
		lo = 0;
		hi = n-1; 
		int best2 = -1;
		while(lo <= hi) {
			int mid = (lo+hi)/2;
		//	cout<<mid<<' '<<"LASD\n";
			for(int i = 0; i < t.size(); ++i) {
		//		cout<<t[i]<<' '<<sa2[mid]<<' '<<s2[sa2[mid]+i]<<endl;
				if(t[i] > s[sa[mid]+i]) { 
					break;	
				}
				if(t[i] < s[sa[mid]+i]) {
		//			cout<<"LOL "<<endl;
					goto ohi2;
				}
			}
			lo = mid+1;
			best2 = mid;
			continue;
			ohi2:;
			hi =mid-1;
		}
		//cout<<best<<' '<<best2<<endl;
		cout<<max(0, best2-best+1)<<endl;
	}

}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED