Substrings

input/code.cpp: In function 'int main()':
input/code.cpp:40:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<s.size(); ++i) st.push_back(i);
                          ^
input/code.cpp:42:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<s.size(); ++i){
                          ^
input/code.cpp:49:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int ii=1; ii<st.size(); ++ii){
                             ^
input/code.cpp:52:9: warning: unused variable 'c' [-Wunused-variable]
     int c=lcp(i, j);
         ^

#include <bits/stdc++.h>
using namespace std;
string s;

long long hsh[101010];
long long ak[101010];
// long long A=999999937;
long long A=37;
long long B=1000000007;


inline long long ghsh(int p, int l){
//   cout << p << "; " << l << ", " << hsh[p+l] << " " << (ak[l]*hsh[p]) << " " << ak[101000-p] << endl;
//   cout << "BEFORE POSITION SHIFT: " << ((hsh[p+l]-((ak[l]*hsh[p])%B)+B)%B) << endl;
  return (hsh[p+l]-((ak[l]*hsh[p])%B)+B)%B;
}

inline int lcp(int a, int b){
  int l=0;
  int r=s.size()-(max(a, b))-1;
  while (l<r){
    int m=(l+r+1)/2;
    if (ghsh(a, m)==ghsh(b, m)) l=m;
    else r=m-1;
  }
  return l;
}

bool cmp(const int& a, const int& b){
  int c=lcp(a, b);
  return s[a+c]<s[b+c];
}

vector<int> st;

int main(){
  ak[0]=1; for (int i=1; i<101010; ++i) ak[i]=ak[i-1]*A%B;
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> s;
  for (int i=0; i<s.size(); ++i) st.push_back(i);
  s.push_back('#');
  for (int i=0; i<s.size(); ++i){
    hsh[i+1]=(hsh[i]*A+s[i])%B;
  }
  
  sort(st.begin(), st.end(), cmp);
  long long ans=0;
  ans=s.size()-st[0]-1;
  for (int ii=1; ii<st.size(); ++ii){
    int j=st[ii-1];
    int i=st[ii];
    int c=lcp(i, j);
    ans+=s.size()-i-1-lcp(i, j);
  }
  cout << ans << "\n";
}

Test 1

Verdict: TIME LIMIT EXCEEDED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: TIME LIMIT EXCEEDED

Test 4

Verdict: TIME LIMIT EXCEEDED