尋找最佳解決方案的Trie數據結構

Question

這個問題是正在進行的競爭的一部分，我已經解決了這個問題數據集的75％，但是25％給了我TLE。我問爲什麼它是給TLE的，我相信我的複雜性是O(n*n)

問：由N小寫英文字母的

字符串s。我們已經準備了一張清單L，由all non empty substrings of the string S組成。

現在他問你Q個問題。到第i個問題，你需要計數的方式的數量來選擇從L

正是文等於字符串，例如：

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


我的做法

我使IT的TRIE和計算和陣列F [i]其中F [i]表示我等於字符串發生的次數。 我TRIE：

static class Batman{ 

     int value; 
     Batman[] next = new Batman[26]; 

     public Batman(int value){ 
      this.value = value; 
      } 
} 

MY插入函數

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

} 

我的主要功能

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

爲什麼我appraoch是給TLE的時間複雜度爲O（ N * N）和String的長度是N < = 5000。請幫我Working CODE

Answer 1

一個原因這一計劃得到TLE（記住，時間限制爲1秒）：

每次創建一個Batman對象時，它會創建一個長度[26]數組，因此，您的時間複雜度爲26 * 5000 * 5000 = 650000000 = 6.5 * 10^8操作，理論上，如果CPU速度爲每秒10^9次的操作，但是也要記住在這之後還有一些計算量很大的東西，所以這應該是原因。

爲了解決這個問題，我用Z-algorithm並得到接受：Link

實際的代碼是相當複雜的，這樣的想法是，你有一個表count[i][j]，這是子串匹配的子（我數，j）。使用Z算法，您可以具有O（n^2）的時間複雜度。

對於每個字符串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-算法方法：

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

實際代碼：http://ideone.com/5GYWeS

說明：

首先，我們有一個數組lengt小時，length[i]是與字符串相匹配的最長子從指數i

開始對每一個指標i，計算後在Z功能，我們可以看到，if cur[i][j] > length[j + i]，這意味着，還有比匹配的先前子存在一個子長在索引j + i，我們沒有把它們計算在我們的結果中，所以我們需要對它們進行計數。

所以，即便有3個嵌套的循環，但每個子只計算一次，這使得這整個時間複雜度爲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]; 
      }   
     } 

對於下面循環中，我們注意到，如果匹配子字符串（i，j），length[i] >= length of substring (i,j)，但是如果沒有匹配，我們需要加1來計數子字符串（i，j），因爲這個子字符串是唯一的。

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