Letter Islands


Problem Statement :


You are given string s  and number k.

Consider a substring  of string . For each position of string  mark it if there is an occurence of the substring that covers the position. More formally, position  will be marked if there exists such index  that:  and . We will tell  produce  islands if all the marked positions form  groups of contiguous positions.

For example, if we have a string ababaewabaq the substring aba marks the positions 1, 2, 3, 4, 5, 8, 9, 10; that is XXXXXewXXXq (X denotes marked position). We can see 2 groups of contiguous positions, that is 2 islands. Finally, substring aba produces 2 islands in the string ababaewabaq.

Calculate and print the number of different substrings of string  that produce exactly  islands.

Input Format

The first line contains string  . The string consists of lowercase letters only. The second line contains an integer  .

Output Format

Output a single integer  the answer to the problem.



Solution :



title-img


                            Solution in C :

In   C++  :









#undef NDEBUG
#ifdef ssu1

#endif

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <bitset>
#include <sstream>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); ++i)
#define forn(i, n) fore(i, 0, n)
#define fori(i, l, r) fore(i, l, (r) + 1)
#define sz(v) int((v).size())
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define mp make_pair
#define X first
#define Y second

template<typename T> inline T abs(T a)
{ return ((a < 0) ? -a : a); }
template<typename T> inline T sqr(T a)
{ return a * a; }

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

const int NMAX = 110000;

struct node{
int l, r, par, link;
map<char, int> next;

node(){
l = r = par = link = -1;
}

node(int _l, int _r, 
int _par) : l(_l), r(_r), par(_par){
link = -1;
}
};

struct tpos{
int V, L;
tpos(int _V, int _L) : V(_V), L(_L) {} 
};


char s[NMAX];
node t[2 * NMAX + 1];
int szt, szs;

int leng(int v){
return t[v].r - t[v].l;
}

int add_edge_to_parent(int l, int r, int parent){
int nidx = szt++;
t[nidx] = node(l, r, parent);
return (t[parent].next[s[l]] = nidx);
}

int split_edge(tpos pos){
int v = pos.V, up = pos.L, down = leng(v) - up;

if(up == 0) return v;
if(down == 0) return t[v].par;

int mid = add_edge_to_parent(t[v].l, 
t[v].l + down, t[v].par);
t[v].l += down, t[v].par = mid;
t[mid].next[s[t[v].l]] = v;
return mid;
}

tpos read_char(tpos pos, char c){
int v = pos.V, up = pos.L;
if(up > 0)
return s[t[v].r - up] == c ? 
tpos(v, up - 1) : tpos(-1, -1);
else{
int nextv = t[v].next.count(c) ?
 t[v].next[c] : -1;
return nextv != -1 ? 
tpos(nextv, leng(nextv) - 1) : tpos(-1, -1);
}
}

tpos fast_go_down(int v, int l, int r){
if(l == r) return tpos(v, 0);
while(true){
v = t[v].next[s[l]];
if(leng(v) >= r - l)
return tpos(v, leng(v) - r + l);
l += leng(v);
}
throw;
}

int link(int v){
if(t[v].link == -1)
t[v].link = split_edge(
    fast_go_down(link(t[v].par), 
    t[v].l + int(t[v].par == 0), t[v].r));
return t[v].link;
}

tpos add_char_to_tree(tpos pos, int i){
while(true){
tpos npos = read_char(pos, s[i]);
if(npos.V != -1) return npos;

int mid = split_edge(pos);

add_edge_to_parent(i, szs, mid);

pos = tpos(link(mid), 0);

if(mid == 0)
return pos;
}
throw;
}

void make_tree(){
szt = 0;
node root(-1, -1, -1); root.link = 0;
t[szt++] = root;

tpos pos(0, 0);
forn(i, szs){
pos = add_char_to_tree(pos, i);
}
}

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

int K;
li result = 0;
typedef tree<pt, null_type,
 less<pt>, rb_tree_tag, 
 tree_order_statistics_node_update> treap;

struct data{
treap* t;
map<int, int>* cnt;
set<int>* positions;

data(){
t = new treap();
cnt = new map<int, int>();
positions = new set<int>();
}

void in_t(int x){
(*cnt)[x]++;
t->insert(mp(x, (*cnt)[x]));
}

void er_t(int x){
t->erase(mp(x, (*cnt)[x]));
(*cnt)[x]--;
}

void insert(int value){
(*positions).insert(value);
set<int>::iterator it = positions->lower_bound(value);

if(it != positions->begin()){
set<int>::iterator prev = it;
prev--;
in_t((*it) - (*prev));
}

if(it != positions->end()){
set<int>::iterator next = it;
next++;
if(next != positions->end()){
in_t((*next) - (*it));
}
}

if(it != positions->begin() && it != positions->end()){
set<int>::iterator prev = it, next = it;
prev--, next++;
if(next != positions->end()){
er_t((*next) - (*prev));
}
}
}

int get_less(int key){
return (int)t->order_of_key(mp(key, -1));
}

void clear(){
t->clear();
cnt->clear();
positions->clear();
}
};

int islands(data t, int ln){
return (int)(t.positions->size() - t.get_less(ln + 1));
}

void dfs(int v, int ln, data& ord){
if(t[v].next.empty()){
ord.insert(szs - ln);
}
data cur;
for(map<char, int>::iterator it = 
t[v].next.begin();
 it != t[v].next.end(); it++){
int u = it->Y;
dfs(u, ln + leng(u), cur);
if(cur.positions->size() > ord.positions->size())
swap(cur, ord);

for(set<int>::iterator jt =
 cur.positions->begin(); 
 jt != cur.positions->end(); jt++){
ord.insert(*jt);
}

cur.clear();
}



if(ln > 0){
int ansL = -1, ansR = -1;
{
int lf = ln - leng(v) + 1, rg = ln;
while(rg - lf > 1){
int mid = (lf + rg) >> 1;
if(islands(ord, mid) > K)
lf = mid;
else
rg = mid;
}
for(int x = lf; x <= rg; x++){
if(islands(ord, x) == K){
ansL = x;
break;
}
}
}
{
int lf = ln - leng(v) + 1, rg = ln;
while(rg - lf > 1){
int mid = (lf + rg) >> 1;
if(islands(ord, mid) < K)
rg = mid;
else
lf = mid;
}
for(int x = rg; x >= lf; --x){
if(islands(ord, x) == K){
ansR = x;
break;
}
}
}
if(ansL != -1){
result += ansR - ansL + 1;

}
}
}

#include <sys/resource.h>

void init_stack(){
const rlim_t kStackSize = 512 * 1024 * 1024;
struct rlimit rl;
int result;

result = getrlimit(RLIMIT_STACK, &rl);
if (result == 0)
{
if (rl.rlim_cur < kStackSize)
{
rl.rlim_cur = kStackSize;
result = setrlimit(RLIMIT_STACK, &rl);
if (result != 0)
{
fprintf(stderr, 
"setrlimit returned result = %d\n", result);
}
}
}
}

int main() {
#ifdef ssu1
assert(freopen("input.txt", "rt", stdin));
#endif

init_stack();

gets(s);
szs = (int)strlen(s);
s[szs++] = '$';

make_tree();

assert(scanf("%d", &K) == 1);

data ord;

dfs(0, 0, ord);

if(K == 1){
result -= szs;
}

cout << result << endl;
#ifdef ssu1
cerr << "\nTime = " << double(
    clock()) / CLOCKS_PER_SEC << endl;
#endif    
return 0;
}









In   Java  :








import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {


public static void main(String[] args) {

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();
}
}
}
}









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;
}









In    Python3 :







from collections import defaultdict


class LetterIslands:
    
    def __init__(self):
        self.s = 0
        self.k = 0
        self.n = 0
        self.result = 0

    def get_indice(self):
        cache = defaultdict(list)
        for (idx,let) in enumerate(self.s):
            cache[let].append(idx)
        for (key,val) in cache.items():
            l = len(val)
            if l < self.k:
                continue
            else:
                for i in range(len(val)-1):
                    if val[i+1] - val[i] <= 1:
                        l -= 1
                if l == self.k:
                    self.result += 1    
        return cache
    
    def get_result(self):
        for (let, pos) in self.get_indice().items():
            len_ = 1
            arr = [[let, pos]]
            while len(arr) > 0:
                dict_ = defaultdict(list)
                temp = []
                for t in arr:
                    for indice in t[1]:
                        try:
                            dict_[t[0] + self.s[indice + len_]].append(indice)
                        except:
                            pass
                len_ = len_+1
                for (key,val) in dict_.items():
                    l = len(val)
                    if l < self.k:
                        continue
                    else:
                        i = 0
                        lenVal = len(val)
                        while l >= self.k and i < lenVal-1:
                            if val[i+1] - val[i] <= len_:
                                l -= 1        
                            i += 1
                        if l == self.k:
                            self.result += 1    
                        if l >= self.k - 1:
                            temp.append([key,val])                
                arr = temp

        return (self.result)


    def debug(self):
        try:
            self.solve()
            print(self.result)
        except:
            pass

    
    def solve(self):
        self._input()
        self.get_result()


    def _input(self):
        self.s = input()
        self.k = int(input()) 
        self.n = len(self.s)


if __name__ == "__main__":
    LetterIslands().debug()
                        








View More Similar Problems

Find Merge Point of Two Lists

This challenge is part of a tutorial track by MyCodeSchool Given pointers to the head nodes of 2 linked lists that merge together at some point, find the node where the two lists merge. The merge point is where both lists point to the same node, i.e. they reference the same memory location. It is guaranteed that the two head nodes will be different, and neither will be NULL. If the lists share

View Solution →

Inserting a Node Into a Sorted Doubly Linked List

Given a reference to the head of a doubly-linked list and an integer ,data , create a new DoublyLinkedListNode object having data value data and insert it at the proper location to maintain the sort. Example head refers to the list 1 <-> 2 <-> 4 - > NULL. data = 3 Return a reference to the new list: 1 <-> 2 <-> 4 - > NULL , Function Description Complete the sortedInsert function

View Solution →

Reverse a doubly linked list

This challenge is part of a tutorial track by MyCodeSchool Given the pointer to the head node of a doubly linked list, reverse the order of the nodes in place. That is, change the next and prev pointers of the nodes so that the direction of the list is reversed. Return a reference to the head node of the reversed list. Note: The head node might be NULL to indicate that the list is empty.

View Solution →

Tree: Preorder Traversal

Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's

View Solution →

Tree: Postorder Traversal

Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the

View Solution →

Tree: Inorder Traversal

In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func

View Solution →