In this HackerEarth Shil and LCP Pairs problem solution Shil came across N strings - s1 , s2 , s3 .. sN . He wants to find out total number of unordered pairs (i, j) such that LCP(si , sj) = k. You have to do thi for every k in [0, L]. Here L = max ( len(si) ) and LCP denotes longest common prefix.


HackerEarth Shil and LCP Pairs problem solution


HackerEarth Shil and LCP Pairs problem solution.

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define pi pair<ll,ll>
#define pii pair<pi,int>
#define f first
#define s second
#define pb push_back
struct trie{
int f;
trie* child[26];
};
ll A[100011];
trie* insert(trie*t,string &s,int i){

if(i==s.length()){
t->f++;
return t;
}

if(t->child[s[i]-'a']==NULL){
t->child[s[i]-'a']=new trie();
t->child[s[i]-'a']->f=0;
}

t->f-=t->child[s[i]-'a']->f;
t->child[s[i]-'a']=insert(t->child[s[i]-'a'],s,i+1);
t->f+=t->child[s[i]-'a']->f;

return t;
}
void calc(trie* t,int d){
if(t==NULL) return;
ll cnt=0;
ll cnt1=0;
ll r;
rep(i,26){
if(t->child[i]){
r=t->child[i]->f;
cnt+=r;
cnt1+=r*r;
calc(t->child[i],d+1);
}
}
r=cnt*cnt-cnt1;
r/=2;
A[d]+=r;
r = t->f - cnt;
A[d]+=r*cnt;
A[d]+=(r*(r-1))/2;
}
int main(){

freopen("input-15.txt","r",stdin);
freopen("output-15.txt","w",stdout);
int N;
cin >> N;
string s[N];
trie*t=new trie();
int maxlen=0;
rep(i,N){
cin >> s[i];
maxlen=max(maxlen,(int)s[i].size());
t=insert(t,s[i],0);
}
calc(t,0);
rep(i,maxlen+1){
cout<<A[i]<<" ";
}
}