# 寻找最优解的Trie数据结构

<登记/> 字符串S由N个小写英文字母组成。我们准备了一份由`all non empty substrings of the string S`组成的清单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 .
``````

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

#### 1 个答案:

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

<强>解释

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

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

0条回复