HackerRank Super Functional Strings problem solution YASH PAL, 31 July 2024 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. Topics we are covering Toggle Problem solution in Python.Problem solution in Java.Problem solution in C++.Problem solution in C. 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("%dn",x) #define pr2(x,y) printf("%d %dn",x,y) #define pr3(x,y,z) printf("%d %d %dn",x,y,z) #define prll1(x) printf("%lldn",x) #define prll2(x,y) printf("%lld %lldn",x,y) #define prll3(x,y,z) printf("%lld %lld %lldn",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("%lldn",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 Algorithms coding problems solutions