This Question is part of ongoing Competition , I have solved the 75% of this Question Data Set but the 25% is giving me TLE. I am asking why it's is giving TLE
an i am sure my complexity is O(n*n)
Question:
String S consisting of N lowercase English alphabets. We has prepared a list L consisting of all non empty substrings of the string S
.
Now he asks you Q questions. To ith question, you need to count the number of ways to choose exactly Ki equal strings from the 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 .
Question LINK
My approach
I am making a TRIE of IT and Calculating The and Array F[i] where F[i] represent the number of times i equal 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 My appraoch is giving TLE as time Complexity is O(N*N) ans the length of String is N<=5000. Please Help me Working CODE
One reason this program get TLE (keep in mind that time constraint is 1 sec):
Each time you create a
Batman
object, it will create an array with length [26], and it is equivalence to adding a loop with n = 26.So, you time complexity is 26*5000*5000 = 650000000 = 6.5*10^8 operations, theoretically, it can still fit into time limit if CPU speed is 10^9 operations per sec, but also keep in mind that there are some heavy calculation stuffs after this, so, this should be the reason.
To solve this problem, I used Z-algorithm and get accepted: Link
The actual code is quite complex, so the idea is, you have a table
count[i][j]
, which is the number of substring that matched substring (i, j). Using Z-algorithm, you can have a time complexity of O(n^2).For each string
s
:Z-algorithm method:
Actual code: http://ideone.com/5GYWeS
Explanation:
First, we have an array length, with
length[i]
is the longest substring that matched with the string start from indexi
For each index
i
, after calculate the Z function, we see that,if cur[i][j] > length[j + i]
, which means, there exists one substring longer than previous substring matched at indexj + i
, and we havent counted them in our result, so we need to count them.So, even there are 3 nested for loop, but each substring is only counted once, which make this whole time complexity is O(n ^2)
For below loop, we notice that, if there is a matched for substring (i,j),
length[i] >= length of substring (i,j)
, but if there is no matched, we need to add 1 to count substring (i,j), as this substring is unique.