字符串后缀:从字符串的某个位置开始到字符串末尾的子串。
后缀数组:指将某个字符串的所有后缀按照字典序排序后得到的数组,但数组并不直接保存后缀字符串,只保存对应的其实位置。
S[]="suffixarray"的后缀数组sa[]
i |
sa[i] |
S[sa[i]...] |
0 |
11 |
'\0'(空串) |
1 |
6 |
array |
2 |
9 |
ay |
3 |
2 |
ffixarray |
4 |
3 |
fixarray |
5 |
4 |
ixarray |
6 |
8 |
ray |
7 |
7 |
rray |
8 |
0 |
suffixarray |
9 |
1 |
uffixarray |
10 |
5 |
xarray |
11 |
10 |
y |
后缀数组的构造:利用2倍增的方法计算,O(n(logn)^2)
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAX_N 10005
char strA[MAX_N], strB[MAX_N];
int sufArr[MAX_N], rank[MAX_N], temp[MAX_N];
int len, k;
bool compareSufArr(int i, int j) {
int ri, rj;
if (rank[i] != rank[j]) {
return rank[i] < rank[j];
} else {
ri = i + k <= len ? rank[i + k] : -1;
rj = j + k <= len ? rank[j + k] : -1;
return ri < rj;
}
}
// 构造后缀数组
void constructSufArr(char* str, int* sa) {
int i;
len = strlen(str);
for (i = 0; i <= len; i++) {
sa[i] = i;
rank[i] = i < len ? str[i] : -1;
}
// 倍增计算
for (k = 1; k <= len; k *= 2) {
// 利用rank对sa排序
sort(sa, sa + len + 1, compareSufArr);
// 利用旧的rank计算新的rank
temp[sa[0]] = 0; // '\0'第一小
for (i = 1; i <= len; i++) {
temp[sa[i]] = temp[sa[i - 1]] + (compareSufArr(sa[i - 1], sa[i]) ? 1 : 0);
}
for (i = 0; i <= len; i++) {
rank[i] = temp[i];
}
}
} // O(n(logn)^2)
// 二分
bool containStr(char* str, int* sa, char* maStr) {
int left, right, mid;
int l;
left = 0, right = strlen(str);
l = strlen(maStr);
while (left < right) {
mid = (left + right) / 2;
if (strncmp(str + sa[mid], maStr, l) < 0) {
left = mid + 1;
} else {
right = mid;
}
}
return strncmp(str + sa[right], maStr, l) == 0;
} // O(|maStr|*log(|str|))
int main() {
bool pos;
while (scanf("%s%s", strA, strB) != EOF) {
constructSufArr(strA, sufArr);
pos = containStr(strA, sufArr, strB);
printf("%d\n", pos);
}
return 0;
}
abracadabra ra
abracadabra dabr
binarysearch arry
suffixarray ixa
分享到:
相关推荐
罗穗骞《后缀数组——处理字符串的有力工具》(有算法源码和解题源码) IOI2009论文,有源码,简单易懂,方便学习后缀数组的构造和各种应用。...后缀数组是一种优秀的数据结构,在字符串匹配方面有诸多应用。
罗穗骞《后缀数组——处理字符串的有力工具》(有算法源码和解题源码) IOI2009论文,有源码,简单易懂,方便学习后缀数组的构造和各种应用。...后缀数组是一种优秀的数据结构,在字符串匹配方面有诸多应用。
KMP算法,全称Knuth-Morris-Pratt字符串搜索算法,是一种线性时间复杂度的字符串匹配算法。它的主要思想是在发生不匹配时,能知道部分已经匹配的字符序列的后缀和模式串的前缀存在重复,因此可以利用这些信息避免...
Giovanni Manzini and Paolo Ferragina 吸取了前人多种经验,结合n个算法,组建了最快的sa构建法.2005年新出的算法.是GNU开源项目,竞赛中 1000万的数据是 1 s,文件相当多,不能...如果不会用,就下载本C++ 多串匹配程序包吧
...关于string的小结 kmp extend_kmp ac+trie 后缀数组
部分匹配表是一个数组,其构建方法如下:对于模式串中的每个前缀子串,找出最长的、同时也是后缀的子串(不包括整个前缀子串本身),记录这个最长后缀子串的长度。部分匹配表的每个元素对应模式串的一个位置,存储的...
KMP算法,即Knuth-Morris-Pratt算法,是一个线性时间复杂度的字符串匹配算法。它能在O(n+m)的时间复杂度内完成一个长度为n的文本串S和一个长度为m的模式串T的匹配工作,其中n和m分别代表文本串和模式串的长度。相比...
代码可能包括字符串匹配(KMP/Boyer-Moore)、编辑距离、后缀数组等算法。 数据结构:组织和存储数据的方式,如数组、链表、栈、队列、树、图等。代码实现这些结构的基本操作,以支持高效的数据处理。 数论:研究...
本科参加ACM竞赛的过程中积累下来的一部分算法模板,和自己在PKU上面做的一部分题目。 模板目录结构: 目录: 动态规划 O(n^2)的最长上升子序列 nlogn最长上升子序列 高精度 ... AC自动机实现多串匹配
使用后缀数组提取链码中的重复字符串作为特征编码,应用动态规划算法在近似匹配条件下计算特征编码在链码中的重复频率。最后,以特征编码及其重复频率作为目标的形状特征和尺度特征,使用贝叶斯分类方法对纹理进行...
1.4 C++程序的编写和实现 1.5 关于C++上机实践 习题 第2章 数据类型与表达式 2.1 C++的数据类型 2.2 常量 2.2.1 什么是常量 2.2.2 数值常量 2.2.3 字符常量 2.2.4 符号常量 2.3 变量 2.3.1 什么是变量 2.3.2 ...
1.4 C++程序的编写和实现 1.5 关于C++上机实践 习题 第2章 数据类型与表达式 2.1 C++的数据类型 2.2 常量 2.2.1 什么是常量 2.2.2 数值常量 2.2.3 字符常量 2.2.4 符号常量 2.3 变量 2.3.1 什么是变量 2.3.2 ...
字符串最小表示4 第二章数据结构5 并查集5 HEAP 最小堆5 树状数组6 二维树状数组6 TRIE 字典树6 后缀数组8 LCP 最长公共前缀9 第三章图论11 BELLMAN FORD 11 BELLMAN FORD(队列优化) 11 最短路径DIJKSTRA+HEAP ...
调频索引是压缩后缀数组,可提供快速子字符串查询。 这是一个围绕的 Python 包装器,用于为文本文件的语料库提供 FM-Index。 该模块提供了一种执行大量(例如 10,000)子字符串搜索的有效方法。 为了在语料库上执行...
日期、字符串、文件大小、复数、数组、序数、数字格式等。API 方法逗号将整数转换为每三位包含逗号的字符串。词将大整数转换为友好的文本表示。编号返回 AP(美联社)格式的数字,小于 10 的数字使用单词。自然日...
收集C ++和Java中的算法和数据结构 数据结构 段树 没有递归的段树 ...字符串算法 Knuth-Morris-Pratt算法 Aho-Corasick算法 后缀数组和lcp数组。 为O基数排序算法(N *的log(n)) 后缀数组。 O
| KARP-RABIN 字符串匹配 32 | 基于 KARP-RABIN 的字符块匹配 32 | 函数名: STRSTR 32 | BM 算法的改进的算法 SUNDAY ALGORITHM 32 | 最短公共祖先(两个长字符串) 33 | 最短公共祖先(多个短字符串) 33 ...
leetcode 2 和 c 实践 C++ ###数据结构和算法 大批 加一: # 合并排序数组:# ...字符串匹配: KMP [, ]: , # 位操作 二的幂:# 数学 三的幂:# 必须知道 :# 动态规划:LeetCode#xx、POJ#xx 后缀数组
◆ 详细介绍了数据抽象,强调规范和实现之间的区别 ◆ 广泛介绍了各种面向对象的编程技术 ◆ 重点是核心的数据结构,而不是非必要的C++语言语法 ◆ 说明了类和ADT在问题解决过程中的作用 ◆ 诠释了ADT的主要...