寻找最优解的Trie数据结构

寻找最优解的Trie数据结构,第1张

这个问题是正在进行的比赛的一部分,我已经解决了这个问题数据集的75%,但25%给了我TLE。我在问为什么它会给TLE一个我确定我的复杂性是O(n*n)

问题:
<登记/> 字符串S由N个小写英文字母组成。我们准备了一份由all non empty substrings of the string S组成的清单L.

现在他问你Q问题。对于第i个问题,您需要计算从列表L中选择与Ki相等的字符串的方式的数量 例如:

    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和计算和数组F [i] ,其中F [i]表示我等于字符串发生的次数。 我的TRIE:

 static class Batman{

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

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

我的插入功能

 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

最佳答案:

1 个答案:

答案 0 :(得分:1)

此程序获得TLE的一个原因(请记住,时间限制为1秒):

每次创建Batman对象时,它都会创建一个长度为[26]的数组,它与添加n = 26的循环等效。

所以,你的时间复杂度是26 * 5000 * 5000 = 650000000 = 6.5 * 10 ^ 8次操作,理论上,如果CPU速度为每秒10 ^ 9次操作,它仍然可以适应时间限制,但也要记住在此之后有一些繁重的计算方法,所以,这应该是原因。

要解决此问题,我使用Z-algorithm并获得接受:Link

实际的代码非常复杂,所以我们的想法是,你有一个表count[i][j],它是匹配子字符串(i,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

<强>解释

首先,我们有一个数组长度,length[i]是与索引i

中的字符串开头匹配的最长子字符串

对于每个索引i,在计算Z函数之后,我们看到if cur[i][j] > length[j i],这意味着,存在一个比索引j i上匹配的前一个子字符串更长的子字符串,我们在我们的结果中没有计算它们,所以我们需要计算它们。

所以,即使有3个嵌套for循环,但每个子字符串只计算一次,这使得整个时间复杂度为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]  ;
        }
本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复