# 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());
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 {
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

int t = Integer.parseInt(st.nextToken());

int[][] map = init();

for (int i = 0; i < t; i++) {
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){
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_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)
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)
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=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)
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