Substrings

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

#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<long long> incount(s.g.size());
        vector<int> q(s.g.size());
        vector<long long> 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;
        }
        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;
                dp[i]++;
        }
        cout<<dp[0]-1<<'\n';
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED