HackerRank Letter Islands problem solution YASH PAL, 31 July 2024 In this HackerRank Letter Islands problem solution we have given string s and number k we need to consider a substring of string s so that for each position of string s mark it if there is an occurrence of the substring that covers the position. and then we need to calculate and print the number of different substrings of string s that produce exactly k substrings.Problem solution in Java.import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ Scanner in = new Scanner(System.in); if(in.hasNext()){ final char[] str = in.next().toCharArray(); if(str.length>0 && in.hasNext()){ int k = in.nextInt(); if(k>0 && k<=str.length){ System.out.println((new FoundSubStrings(str, k)).count()); } } } } static class FoundSubStrings { private final char[] str; private final int k; private Map<Long, SubString> curr; private Map<Long, SubString> next; private SubString previousSub=null; private int previousSubParentStartIndex = -1; private int previousSubLen = -1; public FoundSubStrings(char[] str, int k) { this.str = str; this.k = k; curr = new HashMap<>(str.length>32 ? str.length>>1 : str.length); next = new HashMap<>(str.length>32 ? str.length>>1 : str.length); } public long count(){ long countResult = 0; int startIndex; char lastChar = str[0]; int lastCharCount = 0; for(int i=0; i<=str.length; i++){ if(i==str.length || lastChar!=str[i]){ if(lastCharCount>1){ for(int j=i-lastCharCount; j<i-1; j++){ this.add(j, lastChar, i-j); } } this.add(i-1, lastChar); if(i!=str.length){ lastChar = str[i]; lastCharCount = 1; } } else { lastCharCount++; } } this.switchLists(); while(!curr.isEmpty()){ for(SubString subStr : curr.values()){ if(subStr.islands==k){ countResult++; if(k==1 && subStr.size==1){ countResult+=str.length-subStr.startIndex-subStr.len; continue; } } else if(subStr.size<k){ continue; } for(int i=0; i<subStr.size && ((startIndex=subStr.indexes[i])<(str.length-subStr.len)); i++){ this.add(subStr.startIndex, startIndex, str[startIndex+subStr.len], subStr.len+1, subStr.size); } } this.switchLists(); } return countResult; } private void add(int parentStartIndex, int startIndex, char chr, int len, int childsLength){ if(previousSubParentStartIndex!=parentStartIndex || previousSubLen!=len || previousSub.chr!=chr){ long key = getKey(parentStartIndex, len, chr); previousSub = next.get(key); if(previousSub==null){ previousSub = new SubString(parentStartIndex, startIndex, chr, len, childsLength); next.put(key, previousSub); } previousSubParentStartIndex = previousSub.parentStartIndex; previousSubLen = len; } previousSub.addIndex(startIndex); } private void add(int startIndex, char chr, int len){ long key = getKey(len, chr); SubString sub = next.get(key); if(sub==null){ sub = new SubString(startIndex, chr, len); next.put(key, sub); } sub.addIndex(startIndex); } private void add(int startIndex, char chr){ if(previousSub==null || previousSubLen!=1 || previousSub.chr!=chr){ long key = getKey(chr); previousSub = next.get(key); if(previousSub==null){ previousSub = new SubString(startIndex, chr, 1); next.put(key, previousSub); } previousSubLen = 1; } previousSub.addIndex(startIndex); } private void switchLists(){ previousSubParentStartIndex = -1; previousSub = null; Map<Long, SubString> tmp = curr; curr = next; next = tmp; tmp.clear(); } public static long getKey(int parentStartIndex, int length, char chr){ return (((long)parentStartIndex) | ((long)length<<31) | ((long)chr)<<23); } public static long getKey(int length, char chr){ return (((long)length<<31) | (((long)chr)<<23)); } public static long getKey(char chr){ return (((long)chr)<<23); } class SubString implements Comparable<SubString> { private final int parentStartIndex; private final int len; private final char chr; private int startIndex; private int islands = 0; private int[] indexes; private int size = 0; public SubString(int startIndex, char chr, int length) { this(-1, startIndex, chr, length, 16); } public SubString(int startIndex, char chr, int length, int childsLength) { this(-1, startIndex, chr, length, childsLength); } public SubString(int parentStartIndex, int startIndex, char chr, int length, int childsLength) { this.parentStartIndex = parentStartIndex; this.startIndex = startIndex; this.len = length; this.chr = chr; this.indexes = new int[childsLength>16? 16: childsLength+1]; } public void addIndex(int index){ if(size==0 || (indexes[size-1]+len<index)){ islands++; } if(indexes.length==size+1){ int[] tmpArr = new int[indexes.length<<1]; System.arraycopy(indexes, 0, tmpArr, 0, indexes.length); indexes = tmpArr; } indexes[size++] = index; } @Override public int compareTo(SubString o) { return (this.parentStartIndex==o.parentStartIndex) ? chr - o.chr : this.parentStartIndex - o.parentStartIndex; } @Override public String toString() { StringBuilder sb = new StringBuilder(100); sb.append("SubString{startIndex=").append(startIndex).append(", length=") .append(len).append(", islands=") .append(islands).append(", numberOfIndexes=") .append(size).append(", arr="); for(int i=startIndex; i<startIndex+len; i++){ sb.append(str[i]).append(','); } sb.setCharAt(sb.length()-1,'}'); return sb.toString(); } } } } {“mode”:”full”,”isActive”:false} Problem solution in C++.#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <climits> #include <cstring> #include <map> #include <set> #include <stack> #include <utility> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; typedef long long ll; typedef pair<int, int> pii; #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define REP(i, n) for (int i = 0; i < (n); i++) #define ROF(i, a, b) for (int i = (b); --i >= (a); ) struct Pos { static int id; set<int> a; tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> d; int countLT(int key) { return d.order_of_key(pii(key, 0)); } size_t size() { return a.size(); } void insert(int i) { a.insert(i); auto it = a.lower_bound(i); auto prev = it, next = it; if (it != a.begin()) --prev; if (it != a.end()) ++next; if (it != prev) { d.insert(pii{*it-*prev, id++}); if (it != next && next != a.end()) d.erase(d.lower_bound(pii{*next-*prev, 0})); } if (it != next && next != a.end()) d.insert(pii{*next-*it, id++}); } void join(Pos &b) { for (int x: b.a) insert(x); } Pos() = default; Pos(Pos &&b) { a.swap(b.a); d.swap(b.d); } Pos &operator=(Pos &&b) noexcept { a.swap(b.a); d.swap(b.d); return *this; } }; int Pos::id = 0, n, k; ll ans; namespace KoAluru { bool *t; int *b; template<typename T> void bucket(T a[], int n, int k, bool end) { fill_n(b, k, 0); REP(i, n) b[a[i]]++; if (end) FOR(i, 1, k) b[i] += b[i-1]; else { int s = 0; REP(i, k) s += b[i], b[i] = s-b[i]; } } template<typename T> void plus_to_minus(T a[], int sa[], int n, int k) { bucket(a, n, k, false); sa[b[a[n-1]]++] = n-1; REP(i, n-1) { int j = sa[i]-1; if (j >= 0 && ! t[j]) sa[b[a[j]]++] = j; } } template<typename T> void minus_to_plus(T a[], int sa[], int n, int k) { bucket(a, n, k, true); ROF(i, 0, n) { int j = sa[i]-1; if (j >= 0 && t[j]) sa[--b[a[j]]] = j; } } template<typename T> void ka(T a[], int sa[], int n, int k) { t[n-1] = false; ROF(i, 0, n-1) t[i] = a[i] < a[i+1] || a[i] == a[i+1] && t[i+1]; bool minor = 2 * count(t, t+n, false) > n; bucket(a, n, k, minor); fill_n(sa, n, -1); if (minor) { REP(i, n) if (t[i]) sa[--b[a[i]]] = i; plus_to_minus(a, sa, n, k); minus_to_plus(a, sa, n, k); } else { sa[b[a[n-1]]++] = n-1; REP(i, n-1) if (! t[i]) sa[b[a[i]]++] = i; minus_to_plus(a, sa, n, k); plus_to_minus(a, sa, n, k); } int last = -1, name = 0, nn = count(t, t+n, minor); int *sa2, *pi; if (minor) sa2 = sa, pi = sa+n-nn; else sa2 = sa+n-nn, pi = sa; fill_n(b, n, -1); REP(i, n) if (sa[i] >= 0 && minor == t[sa[i]]) { bool diff = last == -1; int p = sa[i]; if (! diff) REP(j, n) { if (last+j >= n || p+j >= n || a[last+j] != a[p+j] || t[last+j] != t[p+j]) { diff = true; break; } else if (j > 0 && (minor == t[last+j] || minor == t[p+j])) break; } if (diff) { name++; last = p; } b[p] = name-1; } nn = 0; REP(i, n) if (b[i] >= 0) pi[nn++] = b[i]; if (name < nn) ka(pi, sa2, nn, name); else REP(i, nn) sa2[pi[i]] = i; ROF(i, 0, nn) t[i] = a[i] < a[i+1] || a[i] == a[i+1] && t[i+1]; nn = 0; bucket(a, n, k, minor); if (minor) { REP(i, n) if (minor == t[i]) pi[nn++] = i; REP(i, nn) sa[i] = pi[sa2[i]]; ROF(i, 0, nn) { int j = sa[i]; sa[i] = -1; sa[--b[a[j]]] = j; } } else { REP(i, n) if (minor == t[i]) pi[nn++] = i; ROF(i, 0, nn) sa[n-nn+i] = pi[sa2[i]]; REP(i, nn) { int j = sa[n-nn+i]; sa[n-nn+i] = -1; sa[b[a[j]]++] = j; } } if (minor) plus_to_minus(a, sa, n, k); else minus_to_plus(a, sa, n, k); } template<typename T> void main(T a[], int sa[], int b[], int n, int k) { if (n > 0) { KoAluru::b = b; t = new bool[n]; ka(a, sa, n, k); delete[] t; } } template<typename T> void calc_rank_lcp(T a[], int sa[], int n, int rank[], int lcp[]) { REP(i, n) rank[sa[i]] = i; int k = 0; lcp[0] = 0; FOR(i, 0, n) if (rank[i]) { for (int j = sa[rank[i]-1]; i+k < n && j+k < n && a[i+k] == a[j+k]; k++); lcp[rank[i]] = k; k && k--; } } void calc_child(int lcp[], int n, int child[]) { stack<int> st; st.push(0); int last = -1; fill_n(child, n, -1); FOR(i, 1, n) { while (lcp[i] < lcp[st.top()]) { last = st.top(); st.pop(); if (lcp[i] <= lcp[st.top()] && lcp[st.top()] != lcp[last]) child[st.top()] = last; } if (last != -1) { child[i-1] = last; last = -1; } st.push(i); } while (0 < lcp[st.top()]) { last = st.top(); st.pop(); if (0 <= lcp[st.top()] && lcp[st.top()] != lcp[last]) child[st.top()] = last; } while (! st.empty()) st.pop(); st.push(0); FOR(i, 1, n) { while (lcp[i] < lcp[st.top()]) st.pop(); if (lcp[i] == lcp[st.top()]) { child[st.top()] = i; st.pop(); } st.push(i); } } void top_down(int sa[], int lcp[], int child[], int l, int h, int ht, Pos &data) { int ht2; if (l == h-1) { ht2 = n-sa[l]; data.insert(sa[l]); } else { int i = l < child[h-1] && child[h-1] < h ? child[h-1] : child[l]; ht2 = lcp[i]; { Pos cur; top_down(sa, lcp, child, l, i, ht2, cur); if (cur.size() > data.size()) swap(cur, data); data.join(cur); } for (; child[i] > i && lcp[child[i]] == lcp[i]; i = child[i]) { Pos cur; top_down(sa, lcp, child, i, child[i], ht2, cur); if (cur.size() > data.size()) swap(cur, data); data.join(cur); } { Pos cur; top_down(sa, lcp, child, i, h, ht2, cur); if (cur.size() > data.size()) swap(cur, data); data.join(cur); } } l = ht+1; h = ht2+1; while (l < h) { int mi = l+h >> 1; if (k < data.size()-data.countLT(mi+1)) l = mi+1; else h = mi; } int from = l; h = ht2+1; while (l < h) { int mi = l+h >> 1; if (k <= data.size()-data.countLT(mi+1)) l = mi+1; else h = mi; } ans += l-from; } }; const int N = 100000; char a[N+1]; int b[N], sa[N], rnk[N], lcp[N], child[N]; int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ scanf("%s%d", a, &k); n = strlen(a); KoAluru::main(a, sa, b, n, 127); KoAluru::calc_rank_lcp(a, sa, n, rnk, lcp); KoAluru::calc_child(lcp, n, child); Pos data; KoAluru::top_down(sa, lcp, child, 0, n, 0, data); printf("%lldn", ans); } {“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' typedef struct _st_node st_node; typedef struct _st_edge st_edge; typedef enum _type{ ONE=1, TWO, BOTH } type; struct _st_node{ st_node *suffix_link; type t; st_edge *edges[A_SIZE+2]; }; struct _st_edge{ int from; int to; int suffix_index; st_node *node; }; typedef struct _ct_node{ int size; int priority; int value; struct _ct_node *left,*right; } ct_node; int sizeOf(ct_node *root); void recalc(ct_node *root); ct_node* merge(ct_node *L,ct_node *R); void split1(int x,ct_node **L,ct_node **R,ct_node *root); void split2(int x,ct_node **L,ct_node **R,ct_node *root); int max(ct_node *root); int min(ct_node *root); void insert(ct_node **root,ct_node *t); void delete(ct_node **root,int x); void full_insert(ct_node **arr,ct_node **diff,ct_node *t); void dfs_aux(ct_node **arr,ct_node **diff,ct_node *t); void dfs(st_node *root,int len_from, int len_to,int suffix_index,ct_node **arr,ct_node **diff); void suffix_tree(st_node *root, char *str,int len,int flag,int offset); int inter(int l1,int l2,int l3,int l4); char str[100001]; int k,len; long long ans; int main(){ st_node root; ct_node *r1,*r2; scanf("%s%d",str,&k); len=strlen(str); memset(&root,0,sizeof(st_node)); suffix_tree(&root,str,len,0,0); dfs(&root,0,0,0,&r1,&r2); printf("%lld",ans); return 0; } int sizeOf(ct_node *root){ return (root)?root->size:0; } void recalc(ct_node *root){ root->size=sizeOf(root->left)+ sizeOf(root->right)+1; return; } ct_node* merge(ct_node *L,ct_node *R){ if(!L) return R; if(!R) return L; if(L->priority>R->priority){ L->right=merge(L->right,R); recalc(L); return L; } R->left=merge(L,R->left); recalc(R); return R; } void split1(int x,ct_node **L, ct_node **R,ct_node *root){ if(!root){ *L=*R=NULL; return; } int curIndex=sizeOf(root->left); ct_node *t; if(curIndex<=x){ split1(x-curIndex-1,&t,R,root->right); root->right=t; recalc(root); *L=root; } else{ split1(x,L,&t,root->left); root->left=t; recalc(root); *R=root; } return; } void split2(int x,ct_node **L, ct_node **R,ct_node *root){ if(!root){ *L=*R=NULL; return; } int curIndex=root->value; ct_node *t; if(curIndex<=x){ split2(x,&t,R,root->right); root->right=t; recalc(root); *L=root; } else{ split2(x,L,&t,root->left); root->left=t; recalc(root); *R=root; } return; } int max(ct_node *root){ if(root->right) return max(root->right); return root->value; } int min(ct_node *root){ if(root->left) return min(root->left); return root->value; } void insert(ct_node **root,ct_node *t){ ct_node *t1,*t2; split2(t->value,&t1,&t2,*root); *root=merge(t1,merge(t,t2)); return; } void delete(ct_node **root,int x){ ct_node *t1,*t2,*t3; split2(x,&t1,&t3,*root); split1(sizeOf(t1)-2,&t1,&t2,t1); *root=merge(t1,t3); return; } void full_insert(ct_node **arr, ct_node **diff,ct_node *t){ int v1,v2; ct_node *t1,*t2,*t3; split2(t->value,&t1,&t2,*arr); if(!t1 && !t2) *diff=NULL; else if(!t1){ v1=min(t2)-t->value; t3=(ct_node*)malloc(sizeof(ct_node)); t3->priority=rand(); t3->value=v1; t3->size=1; t3->left=t3->right=NULL; insert(diff,t3); } else if(!t2){ v1=t->value-max(t1); t3=(ct_node*)malloc(sizeof(ct_node)); t3->priority=rand(); t3->value=v1; t3->size=1; t3->left=t3->right=NULL; insert(diff,t3); } else{ v1=max(t1); v2=min(t2); delete(diff,v2-v1); t3=(ct_node*)malloc(sizeof(ct_node)); t3->priority=rand(); t3->value=t->value-v1; t3->size=1; t3->left=t3->right=NULL; insert(diff,t3); t3=(ct_node*)malloc(sizeof(ct_node)); t3->priority=rand(); t3->value=v2-t->value; t3->size=1; t3->left=t3->right=NULL; insert(diff,t3); } *arr=merge(t1,merge(t,t2)); return; } void dfs_aux(ct_node **arr, ct_node **diff,ct_node *t){ if(!t) return; dfs_aux(arr,diff,t->left); dfs_aux(arr,diff,t->right); t->size=1; t->left=t->right=NULL; full_insert(arr,diff,t); return; } void dfs(st_node *root,int len_from, int len_to,int suffix_index, ct_node **arr,ct_node **diff){ int v1,v2,i; ct_node *p_arr,*p_diff,*pp_arr,*pp_diff,*t1,*t2; if(!root){ p_arr=(ct_node*)malloc(sizeof(ct_node)); p_arr->priority=rand(); p_arr->value=suffix_index; p_arr->size=1; p_arr->left=p_arr->right=NULL; *arr=p_arr; *diff=NULL; return; } p_arr=p_diff=NULL; if(root->edges[A_SIZE]){ dfs(root->edges[A_SIZE]->node,0,0, root->edges[A_SIZE]->suffix_index, &pp_arr,&pp_diff); if(sizeOf(p_arr)<sizeOf(pp_arr)){ dfs_aux(&pp_arr,&pp_diff,p_arr); p_arr=pp_arr; p_diff=pp_diff; } else dfs_aux(&p_arr,&p_diff,pp_arr); } for(i=0;i<A_SIZE;i++) if(root->edges[i]){ dfs(root->edges[i]->node,len_to+1, len_to+root->edges[i]->to-root->edges[i]->from+1, root->edges[i]->suffix_index,&pp_arr,&pp_diff); if(sizeOf(p_arr)<sizeOf(pp_arr)){ dfs_aux(&pp_arr,&pp_diff,p_arr); p_arr=pp_arr; p_diff=pp_diff; } else dfs_aux(&p_arr,&p_diff,pp_arr); } *arr=p_arr; *diff=p_diff; if(len_to){ if(sizeOf(p_arr)<k) return; split1(sizeOf(p_arr)-k-1,&t1,&t2,p_diff); if(!t1 && !t2) ans+=inter(0,100000,len_from,len_to); else if(!t1) ans+=inter(0,min(t2)-1,len_from,len_to); else if(!t2) ans+=inter(max(t1),100000,len_from,len_to); else{ v1=max(t1); v2=min(t2); if(v1!=v2) ans+=inter(v1,v2-1,len_from,len_to); } p_diff=merge(t1,t2); } return; } void suffix_tree(st_node *root, char *str,int len,int flag,int offset){ int a_edge,a_len=0,remainder=0, need_insert,from,max,i; type t; st_node *a_node=root,*pre_node,*t_node,*tt_node,*pp_node=NULL; st_edge *t_edge; if(flag){ max=A_SIZE+1; t=TWO; } else{ max=A_SIZE; t=ONE; } root->t|=t; for(i=offset;i<=offset+len;i++){ need_insert=0; pre_node=NULL; remainder++; if(i==offset+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_node->t|=t; 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; a_node->t|=t; } 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==offset+len){ a_node->edges[max]=(st_edge*)malloc(sizeof(st_edge)); a_node->edges[max]->suffix_index=i-remainder+1; a_node->edges[max]->node=NULL; t_node=tt_node=a_node; } 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; a_node->t|=t; } 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=offset+len-1; t_edge->suffix_index=i-remainder+1; t_edge->node=(st_node*)malloc(sizeof(st_node)); memset(t_edge->node,0,sizeof(st_node)); t_edge->node->edges[max]=(st_edge*)malloc(sizeof(st_edge)); t_edge->node->edges[max]->suffix_index=i-remainder+1; t_edge->node->edges[max]->node=NULL; t_edge->node->t|=t; a_node->edges[str[i]-MIN_C]=t_edge; t_node=a_node; tt_node=t_edge->node; } else{ if(i!=offset+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_node->t|=t; a_len=0; } else a_len++; break; } t_node=(st_node*)malloc(sizeof(st_node)); memset(t_node,0,sizeof(st_node)); t_node->t|=(a_node->edges[a_edge]->node->t|t); 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==offset+len){ t_node->edges[max]=(st_edge*)malloc(sizeof(st_edge)); t_node->edges[max]->suffix_index=i-remainder+1; t_node->edges[max]->node=NULL; tt_node=t_node; } else{ t_edge=(st_edge*)malloc(sizeof(st_edge)); t_edge->from=i; t_edge->to=offset+len-1; t_edge->suffix_index=i-remainder+1; t_edge->node=(st_node*)malloc(sizeof(st_node)); memset(t_edge->node,0,sizeof(st_node)); t_edge->node->edges[max]=(st_edge*)malloc(sizeof(st_edge)); t_edge->node->edges[max]->suffix_index=i-remainder+1; t_edge->node->edges[max]->node=NULL; t_edge->node->t|=t; t_node->edges[str[i]-MIN_C]=t_edge; tt_node=t_edge->node; } } if(pre_node) pre_node->suffix_link=t_node; pre_node=t_node; if(pp_node) pp_node->suffix_link=tt_node; pp_node=tt_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; a_node->t|=t; } 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_node->t|=t; a_edge=str[from]-MIN_C; } } } return; } int inter(int l1,int l2,int l3,int l4){ if(l3>l2 || l1>l4) return 0; if(l3>=l1) if(l4>=l2) return l2-l3+1; else return l4-l3+1; else if(l4>=l2) return l2-l1+1; else return l4-l1+1; } {“mode”:”full”,”isActive”:false} Algorithms coding problems solutions