HackerRank Super Functional Strings problem solution

In this HackerRank Super Functional Strings problem solution, we have given a function F on a string P that consists of N lowercase letters. we need to computer the summation of function F over all possible distinct substrings of S. as the result is large so we need to print it modulo 10 to the power of 9 plus 7.

Problem solution in Python.

from string import ascii_lowercase
from bisect import bisect_left, bisect_right
from itertools import zip_longest, islice

MOD = 7 + 10 ** 9

N = 10 ** 5

sum_pow = [[0] * (N + 1) for k in range(27)]
for k in range(1, 27):
    for n in range(1, N + 1):
        sum_pow[k][n] = (sum_pow[k][n - 1] + pow(n, k, MOD)) % MOD
        
        
def get_sp(left, right, k):
    if left > right or right <= 0:
        return 0
    if left <= 0:
        return sum_pow[k][right]
    return (sum_pow[k][right] + MOD - sum_pow[k][left - 1]) % MOD


def all_occ(s):
    n = len(s)
    occ = [[] for _ in range(26)]
    for i in range(n):
        occ[ord(s[i]) - ord('a')].append(i)
    return occ

def occ_from_i(occ, i):
    occ_i = []
    for j in range(26):
        if len(occ[j]) == 0 or i > occ[j][-1]:
            continue
        first = bisect_left(occ[j], i)
        occ_i.append(occ[j][first])
    return sorted(occ_i)


def sorted_idx(items):
    unique = sorted(set(items))
    idx = dict(zip(unique, range(len(unique))))
    return [idx[v] for v in items]

def suffix_array(s):
    n = len(s)
    k = 1
    sa = sorted_idx(s)
    while max(sa) < n - 1:
        sa = sorted_idx([a * (n + 1) + b + 1 for
                         (a, b) in zip_longest(sa,
                                               islice(sa, k, None),
                                               fillvalue=-1)])
        k <<= 1
    return sa

def lcp_sa(s):
    inv_sa = suffix_array(s)
    n = len(inv_sa)
    sa = [0] * n
    for i in range(n):
        sa[inv_sa[i]] = i
    lcp = [0] * n
    k = 0
    for i in range(n):
        if inv_sa[i] == n - 1:
            k = 0
            continue
        j = sa[inv_sa[i]+1]
        while i + k < n and j + k < n and s[i + k] == s[j + k]:
            k += 1
        lcp[inv_sa[i] + 1] = k
        if k > 0:
            k -= 1
    return sa, lcp

def solve(s):
    n = len(s)
    occ = all_occ(s)
    sa, lcp = lcp_sa(s)
    ans = 0
    #print(sa)
    #print(lcp)
    for i in range(n):
        o = occ_from_i(occ, sa[i])
        t = sa[i] + lcp[i]
        if t >= o[-1]:
            ans = (ans + get_sp(lcp[i] + 1, n - sa[i], len(o))) % MOD
            continue
        k = bisect_right(o, t)
        ans = (ans + get_sp(lcp[i] + 1, o[k] - sa[i], k)) % MOD
        for j in range(k + 1, len(o)):
            ans = (ans + get_sp(o[j - 1] - sa[i] + 1, o[j] - sa[i], j)) % MOD
        
        ans = (ans + get_sp(o[-1] - sa[i] + 1, n - sa[i], len(o))) % MOD
        
    return ans

def sum_p_bf(left, right, k):
    ans = 0
    for n in range(max(left, 1), right + 1):
        ans = (ans + pow(n, k, MOD)) % MOD
    return ans

q = int(input().strip())
for _ in range(q):
    string = input().strip()
    print(solve(string))

{"mode":"full","isActive":false}

Problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {

  static final int MOD = 1_000_000_007;
  static final int MAX = 100000;

  static class Suffix {
    int index;
    int[] rank = new int[2];
  }

  static Comparator<Suffix> cmp =
      (a, b) -> {
        return (a.rank[0] == b.rank[0]) ? a.rank[1] - b.rank[1] : a.rank[0] - b.rank[0];
      };
  
  static int[] invSuff = new int[MAX];
  static int[] suffixArr = new int[MAX];
  static int[] lcp = new int[MAX];
  
  static void buildSuffixArray(char[] txt) {
    int n = txt.length;
    Suffix[] suffixes = new Suffix[n];

    for (int i = 0; i < n; i++) {
      suffixes[i] = new Suffix();
      suffixes[i].index = i;
      suffixes[i].rank[0] = txt[i] - 'a';
      suffixes[i].rank[1] = ((i + 1) < n) ? (txt[i + 1] - 'a') : -1;
    }

    Arrays.sort(suffixes, cmp);

    int[] ind = new int[n];

    for (int k = 4; k < 2 * n; k = k * 2) {
      int rank = 0;
      int prev_rank = suffixes[0].rank[0];
      suffixes[0].rank[0] = rank;
      ind[suffixes[0].index] = 0;

      for (int i = 1; i < n; i++) {
        if (suffixes[i].rank[0] == prev_rank && suffixes[i].rank[1] == suffixes[i - 1].rank[1]) {
          prev_rank = suffixes[i].rank[0];
          suffixes[i].rank[0] = rank;
        } else {
          prev_rank = suffixes[i].rank[0];
          suffixes[i].rank[0] = ++rank;
        }
        ind[suffixes[i].index] = i;
      }

      for (int i = 0; i < n; i++) {
        int nextindex = suffixes[i].index + k / 2;
        suffixes[i].rank[1] = (nextindex < n) ? suffixes[ind[nextindex]].rank[0] : -1;
      }

      Arrays.sort(suffixes, cmp);
    }

    for (int i = 0; i < n; i++) {
      suffixArr[i] = suffixes[i].index;
      invSuff[suffixArr[i]] = i;
    }
  }

  static void kasai(char[] txt) {
    int n = txt.length;
    int k = 0;

    for (int i = 0; i < n; i++) {
      if (invSuff[i] == n - 1) {
        k = 0;
        continue;
      }
      int j = suffixArr[invSuff[i] + 1];
      while (i + k < n && j + k < n && txt[i + k] == txt[j + k]) {
        k++;
      }

      lcp[invSuff[i]] = k;

      if (k > 0) {
        k--;
      }
    }
  }
  
  static long superFunctionalStrings(char[] s, int[][] map) {
    buildSuffixArray(s);
    kasai(s);

    int len = s.length;

    @SuppressWarnings("unchecked")
    Map<Integer, Integer>[] letterPlaceArr = new Map[len];
    letterPlaceArr[len - 1] = new HashMap<>();
    letterPlaceArr[len - 1].put((s[len - 1]) - 'a', len - 1);
    for (int i = len - 2; i >= 0; i--) {
      letterPlaceArr[i] = new HashMap<>(letterPlaceArr[i + 1]);
      letterPlaceArr[i].put(s[i] - 'a', i);
    }

    long result = 0;
    for (int i = 0; i < len; i++) {
      int nowLen = i == 0 ? 0 : lcp[i - 1];

      int startIndex = suffixArr[i];
      
      List<Integer> tempArr = new ArrayList<Integer>(letterPlaceArr[startIndex].values());
      tempArr.add(len);
      Collections.sort(tempArr);

      for (int j = 1, tempLen = tempArr.size(); j < tempLen; j++) {
        if (tempArr.get(j) - startIndex <= nowLen) {
          continue;
        }

        int diff =
            map[tempArr.get(j) - startIndex][j] - map[Math.max(tempArr.get(j-1) - startIndex, nowLen)][j];
        if (diff < 0) {
          diff += MOD;
        }
        result = (result + diff) % MOD;
      }
    }

    return result;
  }

  static int[][] init() {
    int[][] map = new int[100001][28];
    for (int i = 1; i <= 100000; i++) {
      long temp = 1;
      for (int j = 1; j <= 26; j++) {
        temp = (temp * i) % MOD;
        map[i][j] = (int)temp;
      }
    }

    for (int j = 1; j <= 26; j++) {
      map[0][j] = 0;
      int temp = map[1][j];
      for (int i = 2; i <= 100000; i++) {
        map[i][j] = (temp + map[i][j]) % MOD;
        temp = map[i][j];
      }
    }

    return map;
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int t = Integer.parseInt(st.nextToken());

    int[][] map = init();

    for (int i = 0; i < t; i++) {
      char[] s = br.readLine().toCharArray();
      long result = superFunctionalStrings(s, map);

      bw.write(String.valueOf(result));
      bw.newLine();
    }
    
    bw.close();
    br.close();
  }
}

{"mode":"full","isActive":false}

Problem solution in C++.

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

#define ft first
#define sd second
#define pb push_back
#define all(x) x.begin(),x.end()

#define ll long long int
#define vi vector<int>
#define vii vector<pair<int,int> >
#define pii pair<int,int>
#define vl vector<ll>
#define vll vector<pair<ll,ll> >
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define mp make_pair
#define ms(A, v) memset(A, v, sizeof A)

#define sc1(x) scanf("%d",&x)
#define sc2(x,y) scanf("%d%d",&x,&y)
#define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define scll1(x) scanf("%lld",&x)
#define scll2(x,y) scanf("%lld%lld",&x,&y)
#define scll3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)

#define pr1(x) printf("%d\n",x)
#define pr2(x,y) printf("%d %d\n",x,y)
#define pr3(x,y,z) printf("%d %d %d\n",x,y,z)

#define prll1(x) printf("%lld\n",x)
#define prll2(x,y) printf("%lld %lld\n",x,y)
#define prll3(x,y,z) printf("%lld %lld %lld\n",x,y,z)

#define pr_vec(v) for(int i=0;i<v.size();i++) cout << v[i] << " " ;

#define f_in(st) freopen(st,"r",stdin)
#define f_out(st) freopen(st,"w",stdout)

#define fr(i, a, b) for(i=a; i<=b; i++)
#define fb(i, a, b) for(i=a; i>=b; i--)

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

const int mod = 1e9 + 7;
const int maxn = 500100;

char txt[ maxn ];
int iSA[maxn], SA[maxn]; //output
int cnt[maxn], next_gen[maxn], lcp[maxn], LCP[maxn][22]; //internal
bool bh[maxn], b2h[maxn];
int len;

void reset( int len ) {
    int i; fr(i, 0, len) {
        iSA[i] = 0;
        SA[i] = 0;
        cnt[i] = 0;
        next_gen[i] = 0;
        lcp[i] = 0;
        ms(LCP[i], 0);
        bh[i] = 0;
        b2h[i] = 0;
    }
}

bool smaller_first_char(int a, int b){
    return txt[a] < txt[b];
}

void SuffixSort(int n) {
    for (int i=0; i<n; ++i){
        SA[i] = i;
    }
    sort(SA, SA + n, smaller_first_char);
    for (int i=0; i<n; ++i){
        bh[i] = i == 0 || txt[SA[i]] != txt[SA[i-1]];
        b2h[i] = false;
    }
    for (int h = 1; h < n; h <<= 1){
        int buckets = 0;
        for (int i=0, j; i < n; i = j){
            j = i + 1;
            while (j < n && !bh[j]) j++;
            next_gen[i] = j;
            buckets++;
        }
        if (buckets == n) break;
        for (int i = 0; i < n; i = next_gen[i]){
            cnt[i] = 0;
            for (int j = i; j < next_gen[i]; ++j){
                iSA[SA[j]] = i;
            }
        }
        cnt[iSA[n - h]]++;
        b2h[iSA[n - h]] = true;
        for (int i = 0; i < n; i = next_gen[i]){
            for (int j = i; j < next_gen[i]; ++j){
                int s = SA[j] - h;
                if (s >= 0){
                int head = iSA[s];
                iSA[s] = head + cnt[head]++;
                b2h[iSA[s]] = true;
                }
            }

            for (int j = i; j < next_gen[i]; ++j){
                int s = SA[j] - h;
                if (s >= 0 && b2h[iSA[s]]){
                    for (int k = iSA[s]+1; !bh[k] && b2h[k]; k++) b2h[k] = false;
                }
            }
        }

        for (int i=0; i<n; ++i){
            SA[iSA[i]] = i;
            bh[i] |= b2h[i];
        }
    }
    for (int i=0; i<n; ++i){
        iSA[SA[i]] = i;
    }
}

void InitLCP(int n) {
    for (int i=0; i<n; ++i) 
        iSA[SA[i]] = i;
    lcp[0] = 0;
    for (int i=0, h=0; i<n; ++i)
    {
        if (iSA[i] > 0)
        {
            int j = SA[iSA[i]-1];
            while (i + h < n && j + h < n && txt[i+h] == txt[j+h]) 
                h++;
            lcp[iSA[i]] = h;
            if (h > 0) 
                h--;
        }
    }
}

void ConstructLCP() {
    InitLCP( len );
    for(int i = 0;i<len;++i)
        LCP[i][0] = lcp[i];
    for(int j = 1;(1<<j)<=len;++j){
        for(int i = 0;i+(1<<j)-1<len;++i){
            if(LCP[i][j-1]<=LCP[i+ ( 1<<(j-1) )][j-1])
                LCP[i][j] = LCP[i][j-1];
            else
                LCP[i][j] = LCP[i+(1<<(j-1))][j-1];
        }
    }
}

int GetLCP(int x, int y) {
    if(x == y) return len-SA[x];
    if(x > y) swap(x,y);
    int log = 0;
    while((1<<log)<=(y-x)) ++log;
    --log;
    return min(LCP[x+1][log],LCP[y-(1<<log)+1][log]);
}

const int maxm = 1e5 + 10;
int val[30][maxm];

void pre() {
    int i, j;
    fr(i, 1, 100000) {
        int v = 1;
        fr(j, 0, 26) {
            val[j][i] = v;
            v = 1LL * v * i % mod;
        }
    }
    fr(i, 1, 26) {
        fr(j, 1, 100000) {
            val[i][j] += val[i][j-1];
            if( val[i][j] >= mod ) {
                val[i][j] -= mod;
            }
        }
    }
}

int get(int l, int r, int d) {
    if( r < l ) return 0;
    int v = val[d][r] - val[d][l-1];
    if( v < 0 ) v += mod;
    return v;
}

char s[ maxm ];

int dp[ 30 ][ maxm ];

void solve() {
    pre();
    int t; sc1( t );
    while( t-- ) {
        scanf("%s", txt);
        len = strlen(txt);
        reset( len );
        SuffixSort( len );
        ConstructLCP();
        int i, j;

        fr(i, 0, len) 
            fr(j, 1, 26) 
                dp[j][i] = -1;

        fb(i, len-1, 0) {
            fr(j, 1, 26) dp[j][i] = dp[j][i+1];
            dp[txt[i]-'a'+1][i] = i;
        }

        int ans = 0;
        vi b;
        fr(j, 1, 26) {
            if(dp[j][SA[0]] != -1 )
                b.pb(dp[j][SA[0]]);
        }
        b.pb(len);
        sort(all(b));
        int sz = b.size();
        fr(j, 1, sz-1) {
            ans += get(b[j-1]-SA[0]+1, b[j]-SA[0], j);
            if( ans >= mod ) ans -= mod;
        }

        fr(i, 1, len-1) {
            b.clear();
            fr(j, 1, 26) {
                if(dp[j][SA[i]] != -1 )
                    b.pb(dp[j][SA[i]]);
            }
            b.pb(len);
            sort(all(b));
            int sz = b.size();
            fr(j, 1, sz-1) {
                ans += get(max(lcp[i], b[j-1]-SA[i])+1, b[j]-SA[i], j);
                if( ans >= mod ) ans -= mod;
            }
        }
        cout << ans << "\n";
    }
}

int main() {
    solve();
    return 0;
}

{"mode":"full","isActive":false}

Problem solution in C.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define A_SIZE 26
#define MIN_C 'a'
#define MOD 1000000007
typedef struct _st_node st_node;
typedef struct _st_edge st_edge;
struct _st_node{
  st_node *suffix_link;
  st_edge *edges[A_SIZE+1];
};
struct _st_edge{
  int from;
  int to;
  int suffix_index;
  st_node *node;
};
void print(st_node *root,int len);
void suffix_tree(st_node *root,char *str,int len);
long long modPow(long long a,int x);
void sort_a(int*a,int size);
void merge(int*a,int*left,int*right,int left_size, int right_size);
char str[100001];
int dp[100000][26];
long long ans,pows[26][100001];

int main(){
  int T,len,i,j;
  st_node root;
  for(i=0;i<26;i++)
    for(j=1;j<=100000;j++)
      pows[i][j]=(pows[i][j-1]+modPow(j,i+1))%MOD;
  scanf("%d",&T);
  while(T--){
    scanf("%s",str);
    len=strlen(str);
    for(i=0;i<26;i++)
      dp[len-1][i]=-1;
    dp[len-1][str[len-1]-MIN_C]=len-1;
    for(i=len-2;i>=0;i--){
      memcpy(&dp[i][0],&dp[i+1][0],26*sizeof(int));
      dp[i][str[i]-MIN_C]=i;
    }
    suffix_tree(&root,str,len);
    ans=0;
    print(&root,0);
    printf("%lld\n",ans);
  }
  return 0;
}
void print(st_node *root,int len){
  int i,j,idx,from,to,s,dc,last,t,a[26];
  if(!root)
    return;
  for(i=0;i<A_SIZE;i++)
    if(root->edges[i]){
      idx=root->edges[i]->suffix_index;
      from=idx+len;
      to=idx+len+root->edges[i]->to-root->edges[i]->from;
      s=dc=0;
      last=idx+len-1;
      for(j=0;j<26;j++)
        if(dp[idx][j]!=-1 && dp[idx][j]<from)
          dc++;
        else if(dp[idx][j]>=from && dp[idx][j]<=to)
          a[s++]=dp[idx][j];
      sort_a(a,s);
      for(j=0;j<s;j++,dc++){
        t=a[j]-1;
        if(dc)
          ans=(ans+pows[dc-1][t-idx+1]-pows[dc-1][last-idx+1]+MOD)%MOD;
        last=t;
      }
      t=to;
      ans=(ans+pows[dc-1][t-idx+1]-pows[dc-1][last-idx+1]+MOD)%MOD;
      print(root->edges[i]->node,len+root->edges[i]->to-root->edges[i]->from+1);
    }
  return;
}
void suffix_tree(st_node *root,char *str,int len){
  int a_edge,a_len=0,remainder=0,need_insert,from,i;
  st_node *a_node=root,*pre_node,*t_node;
  st_edge *t_edge;
  memset(root,0,sizeof(st_node));
  for(i=0;i<=len;i++){
    need_insert=0;
    pre_node=NULL;
    remainder++;
    if(i==len)
      need_insert=1;
    else if(a_len)
      if(str[a_node->edges[a_edge]->from+a_len]==str[i])
        if(a_node->edges[a_edge]->from+a_len==a_node->edges[a_edge]->to){
          a_node=a_node->edges[a_edge]->node;
          a_len=0;
        }
        else
          a_len++;
      else
        need_insert=1;
    else
      if(a_node->edges[str[i]-MIN_C])
        if(a_node->edges[str[i]-MIN_C]->from==a_node->edges[str[i]-MIN_C]->to)
          a_node=a_node->edges[str[i]-MIN_C]->node;
        else{
          a_edge=str[i]-MIN_C;
          a_len=1;
        }
      else
        need_insert=1;
    if(need_insert)
      for(;remainder>0;remainder--){
        if(!a_len)
          if(i==len){
            a_node->edges[A_SIZE]=(st_edge*)malloc(sizeof(st_edge));
            a_node->edges[A_SIZE]->suffix_index=i-remainder+1;
            a_node->edges[A_SIZE]->node=NULL;
          }
          else{
            if(a_node->edges[str[i]-MIN_C]){
              if(pre_node)
                pre_node->suffix_link=a_node;
              if(a_node->edges[str[i]-MIN_C]->from==a_node->edges[str[i]-MIN_C]->to)
                a_node=a_node->edges[str[i]-MIN_C]->node;
              else{
                a_edge=str[i]-MIN_C;
                a_len=1;
              }
              break;
            }
            t_edge=(st_edge*)malloc(sizeof(st_edge));
            t_edge->from=i;
            t_edge->to=len-1;
            t_edge->suffix_index=i-remainder+1;
            t_edge->node=NULL;
            a_node->edges[str[i]-MIN_C]=t_edge;
            t_node=a_node;
          }
        else{
          if(i!=len && str[a_node->edges[a_edge]->from+a_len]==str[i]){
            if(pre_node)
              pre_node->suffix_link=a_node;
            if(a_node->edges[a_edge]->from+a_len==a_node->edges[a_edge]->to){
              a_node=a_node->edges[a_edge]->node;
              a_len=0;
            }
            else
              a_len++;
            break;
          }
          t_node=(st_node*)malloc(sizeof(st_node));
          memset(t_node,0,sizeof(st_node));
          t_edge=(st_edge*)malloc(sizeof(st_edge));
          t_edge->from=a_node->edges[a_edge]->from+a_len;
          t_edge->to=a_node->edges[a_edge]->to;
          t_edge->suffix_index=a_node->edges[a_edge]->suffix_index;
          t_edge->node=a_node->edges[a_edge]->node;
          from=a_node->edges[a_edge]->from;
          a_node->edges[a_edge]->node=t_node;
          a_node->edges[a_edge]->to=a_node->edges[a_edge]->from+a_len-1;
          t_node->edges[str[t_edge->from]-MIN_C]=t_edge;
          if(i==len){
            t_node->edges[A_SIZE]=(st_edge*)malloc(sizeof(st_edge));
            t_node->edges[A_SIZE]->suffix_index=i-remainder+1;
            t_node->edges[A_SIZE]->node=NULL;
          }
          else{
            t_edge=(st_edge*)malloc(sizeof(st_edge));
            t_edge->from=i;
            t_edge->to=len-1;
            t_edge->suffix_index=i-remainder+1;
            t_edge->node=NULL;
            t_node->edges[str[i]-MIN_C]=t_edge;
          }
        }
        if(pre_node)
          pre_node->suffix_link=t_node;
        pre_node=t_node;
        if(a_node==root && a_len>0){
          if(remainder>1)
            a_edge=str[i-remainder+2]-MIN_C;
          from=i-remainder+2;
          a_len--;
        }
        else if(a_node!=root)
          if(a_node->suffix_link)
            a_node=a_node->suffix_link;
          else
            a_node=root;
        while(a_len>0 && a_len>=a_node->edges[a_edge]->to-a_node->edges[a_edge]->from+1){
          a_len-=a_node->edges[a_edge]->to-a_node->edges[a_edge]->from+1;
          from+=a_node->edges[a_edge]->to-a_node->edges[a_edge]->from+1;
          a_node=a_node->edges[a_edge]->node;
          a_edge=str[from]-MIN_C;
        }
      }
  }
  return;
}
long long modPow(long long a,int x){
  long long res = 1;
  while(x>0){
    if(x%2)
      res=(res*a)%MOD;
    a=(a*a)%MOD;
    x>>=1;
  }
  return res;
}
void sort_a(int*a,int size){
  if (size < 2)
    return;
  int m = (size+1)/2,i;
  int *left,*right;
  left=(int*)malloc(m*sizeof(int));
  right=(int*)malloc((size-m)*sizeof(int));
  for(i=0;i<m;i++)
    left[i]=a[i];
  for(i=0;i<size-m;i++)
    right[i]=a[i+m];
  sort_a(left,m);
  sort_a(right,size-m);
  merge(a,left,right,m,size-m);
  free(left);
  free(right);
  return;
}
void merge(int*a,int*left,int*right,int left_size, int right_size){
    int i = 0, j = 0;
    while (i < left_size|| j < right_size) {
        if (i == left_size) {
            a[i+j] = right[j];
            j++;
        } else if (j == right_size) {
            a[i+j] = left[i];
            i++;
        } else if (left[i] <= right[j]) {
            a[i+j] = left[i];
            i++;                
        } else {
            a[i+j] = right[j];
            j++;
        }
    }
    return;
}

{"mode":"full","isActive":fals