寻找最优解中的 Trie 数据结构
Trie Data Structure in Finding an Optimal Solution
这个问题是正在进行的竞赛的一部分,我已经解决了这个问题数据集的 75%,但是 25% 给我 TLE。我在问为什么它给出 TLE
我确定我的复杂性是 O(n*n)
问题:
由 N 个小写英文字母组成的字符串 S。我们准备了一个列表L,由all non empty substrings of the string S
.
组成
现在他问你Q问题。对于第一个问题,您需要计算从列表 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 的 TRIE 并且 计算 The 和数组 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());
}
}
为什么我的方法在时间复杂度为 O(N*N) 时给出 TLE,字符串的长度为 N<=5000。请帮助我Working CODE
此程序获得 TLE 的原因之一(请记住时间限制为 1 秒):
每创建一个Batman
对象,都会创建一个长度为[26]的数组,相当于增加一个n=26的循环。
所以,你的时间复杂度是26*5000*5000 = 650000000 = 6.5*10^8次操作,理论上,如果CPU速度是每秒10^9次操作,它仍然可以满足时间限制,但也要记住,这之后还有一些繁重的计算工作,所以,这应该是原因。
为了解决这个问题,我使用了Z-algorithm and get accepted: Link
实际代码比较复杂,所以思路是,你有一个tablecount[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;
}
解释:
首先,我们有一个数组长度,其中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, j), 因为这个子串是唯一的。
for(int j = i; j < n; j++){
int v = count[i][j] + (length[i] < (j - i + 1) ? 1 : 0);
F[v]++;
}
这个问题是正在进行的竞赛的一部分,我已经解决了这个问题数据集的 75%,但是 25% 给我 TLE。我在问为什么它给出 TLE
我确定我的复杂性是 O(n*n)
问题:
由 N 个小写英文字母组成的字符串 S。我们准备了一个列表L,由all non empty substrings of the string S
.
组成
现在他问你Q问题。对于第一个问题,您需要计算从列表 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 的 TRIE 并且 计算 The 和数组 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());
}
}
为什么我的方法在时间复杂度为 O(N*N) 时给出 TLE,字符串的长度为 N<=5000。请帮助我Working CODE
此程序获得 TLE 的原因之一(请记住时间限制为 1 秒):
每创建一个Batman
对象,都会创建一个长度为[26]的数组,相当于增加一个n=26的循环。
所以,你的时间复杂度是26*5000*5000 = 650000000 = 6.5*10^8次操作,理论上,如果CPU速度是每秒10^9次操作,它仍然可以满足时间限制,但也要记住,这之后还有一些繁重的计算工作,所以,这应该是原因。
为了解决这个问题,我使用了Z-algorithm and get accepted: Link
实际代码比较复杂,所以思路是,你有一个tablecount[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;
}
解释:
首先,我们有一个数组长度,其中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, j), 因为这个子串是唯一的。
for(int j = i; j < n; j++){
int v = count[i][j] + (length[i] < (j - i + 1) ? 1 : 0);
F[v]++;
}