首页 > 代码库 > 后缀数组解决在线的多模板匹配问题

后缀数组解决在线的多模板匹配问题

终于学会倍增法了, 先一个最水最水的后缀数组应用。

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

  

后缀数组解决在线的多模板匹配问题