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

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

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

from collections import defaultdict
import random
word = raw_input()
k = int(raw_input())
wordLength = len(word)
s = 0

def getIndiceLetter(word,k):
	global s
	indiceLetter = defaultdict(list)
	for (index,letter) in enumerate(word):
		indiceLetter[letter].append(index)
	for (key,value) in indiceLetter.items():
		l = len(value)
		if l < k:
			continue
		else:
			for i in range(len(value)-1):
				if value[i+1] - value[i] <= 1:
					l -= 1
			if l == k:
				s += 1	
	return indiceLetter

for (letter, pos) in getIndiceLetter(word,k).items():
	length = 1
	arrs = [[letter, pos]]
	while len(arrs) > 0:
		dd = defaultdict(list)
		output = []
		for arr in arrs:
			for indice in arr[1]:
				try:
					dd[arr[0] + word[indice + length]].append(indice)
				except:
					pass
		length = length+1
		for (key,value) in dd.items():
			l = len(value)
			if l < k:
				continue
			else:
				i = 0
				valueLen = len(value)
				while l >= k and i < valueLen-1:
					if value[i+1] - value[i] <= length:
						l -= 1		
					i += 1
				if l == k:
					s += 1	
				if l >= k - 1:
					output.append([key,value])				
		arrs = output

print s

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