我们如何从 LCP 阵列构建 LCP-LR 阵列?
How do we Construct LCP-LR array from LCP array?
查找给定字符串 P(长度 m)在文本 T(长度 N)中出现的次数
必须对T的后缀数组使用二分查找
使用标准二进制搜索(没有 LCP 信息)的问题是,在您需要进行的每一次 O(log N) 比较中,您将 P 与后缀数组的当前条目进行比较,这意味着最多 m 个字符的完整字符串比较。所以复杂度是 O(m*log N).
LCP-LR 阵列有助于将其改进为 O(m+log N)。
know more
我们如何从 LCP 阵列预先计算 LCP-LR 阵列?
以及 LCP-LR 如何帮助找到模式的出现次数?
请举例说明算法
谢谢
// note that arrSize is O(n)
// int arrSize = 2 * 2 ^ (log(N) + 1) + 1; // start from 1
// LCP = new int[N];
// fill the LCP...
// LCP_LR = new int[arrSize];
// memset(LCP_LR, maxValueOfInteger, arrSize);
//
// init: buildLCP_LR(1, 1, N);
// LCP_LR[1] == [1..N]
// LCP_LR[2] == [1..N/2]
// LCP_LR[3] == [N/2+1 .. N]
// rangeI = LCP_LR[i]
// rangeILeft = LCP_LR[2 * i]
// rangeIRight = LCP_LR[2 * i + 1]
// ..etc
void buildLCP_LR(int index, int low, int high)
{
if(low == high)
{
LCP_LR[index] = LCP[low];
return;
}
int mid = (low + high) / 2;
buildLCP_LR(2*index, low, mid);
buildLCP_LR(2*index+1, mid + 1, high);
LCP_LR[index] = min(LCP_LR[2*index], LCP_LR[2*index + 1]);
}
参考:
没有足够的代表发表评论,因此发帖。是否有人能够使用@Abhijeet Ashok Muneshwar 解决方案创建 LCP-LR。对于 ex for text- mississippi 后缀数组-
0 1 2 3 4 5 6 7 8 9 10
10 7 1 4 0 9 8 3 6 2 5
LCP 阵列将为
0 1 2 3 4 5 6 7 8 9 10
1 1 4 0 0 1 0 2 1 3 0
LCP-LR 将是
0 1 2 3 4 5 6 7 8 9 10
1 1 0 4 0 0 0 0 0 1 3
但是使用代码得到的LCP-LR和上面的不一样。
对于方法 buildLCP_LR 我正在传递 index=0, low=0, high=n
查找给定字符串 P(长度 m)在文本 T(长度 N)中出现的次数
必须对T的后缀数组使用二分查找
使用标准二进制搜索(没有 LCP 信息)的问题是,在您需要进行的每一次 O(log N) 比较中,您将 P 与后缀数组的当前条目进行比较,这意味着最多 m 个字符的完整字符串比较。所以复杂度是 O(m*log N).
LCP-LR 阵列有助于将其改进为 O(m+log N)。 know more
我们如何从 LCP 阵列预先计算 LCP-LR 阵列?
以及 LCP-LR 如何帮助找到模式的出现次数?
请举例说明算法
谢谢
// note that arrSize is O(n)
// int arrSize = 2 * 2 ^ (log(N) + 1) + 1; // start from 1
// LCP = new int[N];
// fill the LCP...
// LCP_LR = new int[arrSize];
// memset(LCP_LR, maxValueOfInteger, arrSize);
//
// init: buildLCP_LR(1, 1, N);
// LCP_LR[1] == [1..N]
// LCP_LR[2] == [1..N/2]
// LCP_LR[3] == [N/2+1 .. N]
// rangeI = LCP_LR[i]
// rangeILeft = LCP_LR[2 * i]
// rangeIRight = LCP_LR[2 * i + 1]
// ..etc
void buildLCP_LR(int index, int low, int high)
{
if(low == high)
{
LCP_LR[index] = LCP[low];
return;
}
int mid = (low + high) / 2;
buildLCP_LR(2*index, low, mid);
buildLCP_LR(2*index+1, mid + 1, high);
LCP_LR[index] = min(LCP_LR[2*index], LCP_LR[2*index + 1]);
}
参考:
没有足够的代表发表评论,因此发帖。是否有人能够使用@Abhijeet Ashok Muneshwar 解决方案创建 LCP-LR。对于 ex for text- mississippi 后缀数组-
0 1 2 3 4 5 6 7 8 9 10
10 7 1 4 0 9 8 3 6 2 5
LCP 阵列将为
0 1 2 3 4 5 6 7 8 9 10
1 1 4 0 0 1 0 2 1 3 0
LCP-LR 将是
0 1 2 3 4 5 6 7 8 9 10
1 1 0 4 0 0 0 0 0 1 3
但是使用代码得到的LCP-LR和上面的不一样。 对于方法 buildLCP_LR 我正在传递 index=0, low=0, high=n