java - Trie Data Structure in Finding an Optimal Solution -

this question part of ongoing competition , have solved 75% of question data set 25% giving me tle. asking why it's giving tle sure complexity o(n*n)

question:

string s consisting of n lowercase english alphabets. has prepared list l consisting of all non empty substrings of string s.

asks q questions. ith question, need count number of ways choose ki equal strings list l

example:

    string  = ababa l = {"a", "b", "a", "b", "a", "ab", "ba", "ab", "ba", "aba", "bab", "aba", "abab", "baba", "ababa"}. k1 = 2: there 7 ways choose 2 equal strings ("a", "a"), ("a", "a"), ("a", "a"), ("b", "b"), ("ab", "ab"), ("ba", "ba"), ("aba", "aba"). k2 = 1: can choose string l (15 ways). k3 = 3: there 1 way choose 3 equal strings - ("a", "a", "a"). k4 = 4: there no 4 equal strings in l . 

question link


my approach

i making trie of , calculating , array f[i] f[i] represent number of times equal string occur. trie:

 static class batman{          int value;         batman[] next = new batman[26];          public batman(int value){             this.value = value;             }   } 

my insert function

 public static void  insert(string s,int[] f , int start){       batman temp = root;      for(int i=start;i<s.length();i++){          int index = s.charat(i)-'a';           if(temp.next[index]==null){              temp.next[index] = new batman(1);              f[1]+=1;           }else{              temp.next[index].value+=1;              int xx = temp.next[index].value;              f[xx-1]-=1;              f[xx]+=1;              // calculating frequency of equal strings          }          temp = temp.next[index];      }   } 

my main function

public static void main(string args[] ) throws  java.lang.exception  {  root = new batman(0); int n = in.nextint(); int q = in.nextint(); string s = in.next(); int[] f = new int[n+1];  for(int i=0;i<n;i++)     insert(s,f,i);   long[] ans = new long[n+1];   for(int i=1;i<=n;i++){     for(int j=i;j<=n;j++){         ans[i]+= f[j]*c[j][i];  // c[n][k] binomial coffecient         ans[i]%=mod;     } }    while(q>0){      q--;     int cc = in.nextint();     long o =0;     if(cc<=n) o=ans[cc];      system.out.println(o+" "+s.length());  } } 

why appraoch giving tle time complexity o(n*n) ans length of string n<=5000. please me working code

one reason program tle (keep in mind time constraint 1 sec):

each time create batman object, create array length [26], , equivalence adding loop n = 26.

so, time complexity 26*5000*5000 = 650000000 = 6.5*10^8 operations, theoretically, can still fit time limit if cpu speed 10^9 operations per sec, keep in mind there heavy calculation stuffs after this, so, should reason.

to solve problem, used z-algorithm , accepted: link

the actual code quite complex, idea is, have table count[i][j], number of substring matched substring (i, j). using z-algorithm, can have time complexity of o(n^2).

for each string s:

        int n = in.nextint();         int q = in.nextint();         string s = in.next();         int[][] cur = new int[n][];         int[][] count = new int[n][n];         int[] length = new int[n];         (int = 0; < n; i++) {             cur[i] = z(s.substring(i).tochararray());//applying z algorithm             (int j = 1; j < cur[i].length; j++) {                 if (cur[i][j] > length[j + i]) {                     (int k = + length[j + i]; k < + cur[i][j]; k++) {                         count[i][k]++;                     }                     length[j + i] = cur[i][j];                 }              }         }         int[] f = new int[n + 1];         for(int = 0; < n; i++){             for(int j = i; j < n; j++){                 int v = count[i][j] + (length[i] < (j - + 1) ? 1 : 0);                 f[v]++;             }         } 

z-algorithm method:

public static int[] z(char[] s) {     int[] z = new int[s.length];     int n = s.length;     int l = 0, r = 0;     (int = 1; < n; i++) {         if (i > r) {             l = r = i;             while (r < n && s[r - l] == s[r])                 r++;              z[i] = r - l;              r--;         } else {             int k = - l;             if (z[k] < r - + 1) {                 z[i] = z[k];             } else {                 l = i;                 while (r < n && s[r - l] == s[r])                     r++;                 z[i] = r - l;                 r--;             }         }     }     return z; } 

actual code: http://ideone.com/5gywes

explanation:

first, have array length, length[i] longest substring matched string start index i

for each index i, after calculate z function, see that, if cur[i][j] > length[j + i], means, there exists 1 substring longer previous substring matched @ index j + i, , havent counted them in our result, need count them.

so, there 3 nested loop, each substring counted once, make whole time complexity o(n ^2)

        (int j = 1; j < cur[i].length; j++) {             if (cur[i][j] > length[j + i]) {                 (int k = + length[j + i]; k < + cur[i][j]; k++) {                     count[i][k]++;                 }                 length[j + i] = cur[i][j];             }                   } 

for below loop, notice that, if there matched substring (i,j), length[i] >= length of substring (i,j), if there no matched, need add 1 count substring (i,j), substring unique.

        for(int j = i; j < n; j++){             int v = count[i][j] + (length[i] < (j - + 1) ? 1 : 0);             f[v]++;         }