夏晓光(loveJY)的博客

TJOI2017DxTx

铁憨憨又进了一波新图片qwq

然后这道题在我的任务计划里躺了太久很不爽就做掉吧

• 给你两个串,问有多少个l,r满足在第一个串中$S_{l...r}$与第二个串至多相差不超过三个字符,且r-l+1=len_S_{2}
• 字符集小于4

哇偶,一看所有子串类型题就是SAM啦

我们先把SAM给建出来,然后从根节点开始往下搜,dfs函数中记录一下用了几个点,然后长度是什么

一旦长度刚好大于{len_S_2}我们就加上$S_1$中这个子串出现的次数

非常简单的一个搜索就可以了.....复杂度为啥是对的呢?QWQ

具体实现看看代码吧w所以我们就考制胡窜这样的吗???

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

const int MAXN = 1e6 + 7;
char s[MAXN];
int ans, m, val[MAXN];
namespace SAM {
	int cnt[MAXN << 1], fa[MAXN << 1], ch[MAXN << 1][4], len[MAXN << 1], lst, T;
	int a[MAXN], c[MAXN];
	inline void init() {
		memset(SAM::ch, 0, sizeof(ch));
		memset(SAM::cnt, 0, sizeof(cnt));
		T = lst = 1;
	}
	inline void ins(int c) {
		int p = lst;
		int np = lst = ++T;
		len[np] = len[p] + 1;
		cnt[np] = 1;//endpos
		for(; p && !ch[p][c]; p = fa[p])ch[p][c] = np;
		if(!p) {
			fa[np] = 1;
		} else {
			int q = ch[p][c];
			if(len[q] == len[p] + 1)fa[np] = q;
			else {
				int nq = ++T;
				len[nq] = len[p] + 1;
				memcpy(ch[nq], ch[q], sizeof(ch[q]));
				for(; ch[p][c] == q; p = fa[p])ch[p][c] = nq;
				fa[nq] = fa[q];
				fa[q] = fa[np] = nq;
			}
		}
	}
	inline void sort() {
		memset(a, 0, sizeof(a));
		for(int i = 1; i <= T; ++i)++a[len[i]];
		for(int i = 1; i <= T; ++i)a[i] += a[i - 1];
		for(int i = 1; i <= T; ++i)c[a[len[i]]--] = i;
		for(int i = T; i; --i) {
			int p = c[i];
			// printf("%d %d\n", p, fa[p]);
			cnt[fa[p]] += cnt[p];
			//子树中本质不同子串个数
		}
	}
	inline void dfs(int u, int len, int j) {
		if(len > m)return (void)(ans += cnt[u]);//就是这样...
		// printf("%d %d %d?\n", u, len, j);
		for(int i = 0; i < 4; ++i) {
			if(!ch[u][i])continue;
			if(val[s[len]] == i)dfs(ch[u][i], len + 1, j);
			else if(j < 3)dfs(ch[u][i], len + 1, j + 1);//不同?限制不能多选
		}
	}
};



int main() {
	val['T'] = 0;
	val['A'] = 1;
	val['C'] = 2;
	val['G'] = 3;
	int T;
	scanf("%d", &T);
	while(T--) {
		SAM::init();
		ans = 0;
		scanf("%s", s + 1);
		int L = strlen(s + 1);
		for(int i = 1; i <= L; ++i)SAM::ins(val[s[i]]);
		SAM::sort();
		scanf("%s", s + 1);
		m = strlen(s + 1);
		SAM::dfs(1, 1, 0);
		printf("%d\n", ans);
	}
	return 0;
}

$Orzhq$