首页 > 代码库 > 后缀数组解决在线的多模板匹配问题
后缀数组解决在线的多模板匹配问题
终于学会倍增法了, 先一个最水最水的后缀数组应用。
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn = 1e6;char buf[maxn];int str[maxn], len, sa[maxn];inline int idx(char c) { return c - ‘a‘;}int stra[maxn], strb[maxn], strcnt[maxn];void build_sa(int *str, int *sa, int n, int m) { int i, j, *x = stra, *y = strb, *cnt = strcnt, chcnt; //第一次基数排序 for (i = 0; i < m; i++) cnt[i] = 0; for (i = 0; i < n; i++) cnt[x[i] = str[i]]++; for (i = 1; i < m; i++) cnt[i] += cnt[i - 1]; for (i = n - 1; i >= 0; i--) sa[--cnt[x[i]]] = i; //倍增长度排序 for (chcnt = 1, j = 1; chcnt < n; j <<= 1, m = chcnt) { //根据第二关键字排序,可以由上一次得到的sa值获得 for (i = n - j, chcnt = 0; i < n; i++) y[chcnt++] = i; for (i = 0; i < n; i++) if (sa[i] >= j) y[chcnt++] = sa[i] - j; //根据第一关键字排序 for (i = 0; i < m; i++) cnt[i] = 0; for (i = 0; i < n; i++) cnt[x[y[i]]]++; for (i = 1; i < m; i++) cnt[i] += cnt[i - 1]; for (i = n - 1; i >= 0; i--) sa[--cnt[x[y[i]]]] = y[i]; //根据sa值重新计算名次数组 swap(x, y); for (chcnt = 1, x[sa[0]] = 0, i = 1; i < n; i++) { bool eql = y[sa[i]] == y[sa[i - 1]] && y[sa[i] + j] == y[sa[i - 1] + j]; x[sa[i]] = eql ? chcnt - 1 : chcnt++; } }}char dict[maxn];void query(int len) { int l = 0, r = len, ansstr = 0, clen; clen = strlen(dict); while (l <= r) { int mid = (l + r) >> 1; bool ok = !strncmp(dict, buf + sa[mid], clen); if (ok) { ansstr = mid; r = mid - 1; } else l = mid + 1; } for (int i = ansstr; !strncmp(dict, buf + sa[i], clen); i++) { printf("find %s at pos %d\n", dict, sa[i]); }}int main() { while (scanf("%s", buf) != EOF) { len = 0; while (buf[len] != 0) { str[len] = idx(buf[len]); len++; } str[len] = 0; build_sa(str, sa, len + 1, 27); int N; scanf("%d", &N); for (int i = 0; i < N; i++) { scanf("%s", dict); query(len + 1); } } return 0;}
后缀数组解决在线的多模板匹配问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。