Trie data structure in search of the optimal solution
This question is part of an ongoing Competition, I have solved 75% of this dataset of questions, but 25% gives me TLE. I ask why it gives TLE
and I am sure that my difficulty is O(n*n)
Question:
String S consists of N lowercase English alphabets. We have prepared a list L consisting of all non empty substrings of the string S
.
Now he asks you Q questions. With the question, you need to count the number of ways to select exactly equal Ki strings from a list L
For example:
String = ababa
L = {"a", "b", "a", "b", "a", "ab", "ba", "ab", "ba", "aba", "bab", "aba", "abab", "baba", "ababa"}.
k1 = 2: There are seven ways to choose two equal strings ("a", "a"), ("a", "a"), ("a", "a"), ("b", "b"), ("ab", "ab"), ("ba", "ba"), ("aba", "aba").
k2 = 1: We can choose any string from L (15 ways).
k3 = 3: There is one way to choose three equal strings - ("a", "a", "a").
k4 = 4: There are no four equal strings in L .
LINK question
My approach
I am doing TRIE for IT and Calculate and Array F [i] where F [i] represents the number of times String Occur. My 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 The Frequency of I 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] is the 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 is my attribute giving TLE as time. Complexity is O (N * N) and line length is N <= 5000. Please help me Working CODE
source to share
One of the reasons this program gets TLE (remember the time limit is 1 second):
Every time you create an object Batman
, it creates an array with length [26], and this is equivalent to adding a loop with n = 26.
So, the time complexity is 26 * 5000 * 5000 = 650,000,000 = 6.5 * 10 ^ 8 operations, in theory it could still fit into the time limit if the processor speed is 10 ^ 9 operations per second, but also keep in mind, that there are some heavy consumables after that, so that must be the reason.
To solve this problem, I used Z-algorithm and accept: Link
The actual code is rather complicated, so the idea is this: you have a table count[i][j]
that is the number of substrings that match the substring (i, j). Using the Z-Algorithm you can have O (n ^ 2) time complexity.
For each line 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];
for (int i = 0; i < n; i++) {
cur[i] = Z(s.substring(i).toCharArray());//Applying Z algorithm
for (int j = 1; j < cur[i].length; j++) {
if (cur[i][j] > length[j + i]) {
for (int k = i + length[j + i]; k < i + cur[i][j]; k++) {
count[i][k]++;
}
length[j + i] = cur[i][j];
}
}
}
int[] F = new int[n + 1];
for(int i = 0; i < n; i++){
for(int j = i; j < n; j++){
int v = count[i][j] + (length[i] < (j - i + 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;
for (int i = 1; i < 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 = i - L;
if (z[k] < R - i + 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, we have the length of the array, and length[i]
the longest substring that matches the beginning of the string from the indexi
For each index, i
after calculating the Z function, we see that if cur[i][j] > length[j + i]
, which means that there is one substring longer than the previous substring corresponding to the index j + i
, and we did not count them in our result, so we need to count them.
So, even there are 3 nested loops, but each substring is counted only once, which makes all the complexity of this time O (n ^ 2)
for (int j = 1; j < cur[i].length; j++) {
if (cur[i][j] > length[j + i]) {
for (int k = i + length[j + i]; k < i + cur[i][j]; k++) {
count[i][k]++;
}
length[j + i] = cur[i][j];
}
}
In the bottom loop, we notice that if length[i] >= length of substring (i,j)
there is a match for the substring (i, j), then if there is no match, we need to add 1 to count the substring (i, j), since this substring is unique.
for(int j = i; j < n; j++){
int v = count[i][j] + (length[i] < (j - i + 1) ? 1 : 0);
F[v]++;
}
source to share