[EZOJ3608] 字符串匹配

发现同一样东西可以用很多种方法踩过去。
列在这里做思路启发。

问题描述

对于两个等长的字符串s,t，每次可以花费1的代价，将两个字符串中的某一种字符替换成另外一种。
令f(s,t)为最少做多少次这样的操作使得做完之后s=t。
如s=abcd,t=ddcb时将a换成b，b换成d得到s=ddcd,t=ddcd。
现读入两个字符串s,t，对于S中每个长度为|t|的字串s’求f(s’,t)的值。
字符集为a~f，长度$10^5$，时限3秒。

题解

考虑某一位上s’和t不同的话这两个字母经过操作后肯定是一样的。
可以扫一遍，用并查集维护最后最多能有多少种不同的字母。答案就是并查集合并的次数。
但是这样是$O(n^2)$的，需要考虑优化。

神级优化

if(合并次数==5) break;

巧妙地猜测了出题人懒惰的心理，得到期望O(n)的复杂度

低级优化

考虑两个字符x,y之间可不可以连边。
意味着某一位上s’出现了x，t出现了y或s’出现了y，t出现了x。
考虑用6个bitset记录一个字符串哪里出现了什么字符。
然后是否可以连边就对应的bitset相与看看是否为0。
但是因为需要枚举x,y要乘30导致复杂度是$(|s|^2\times 30 /64)$为47亿。
所以手写bitset，使相与的长度为|t|，极限复杂度/=4。
（bitset不可变长，不手写时相与长度为|s|)
然后加sse2指令集优化成一次运算128位
复杂度是$(|s|/2)^2 \times 30 / 128$
大概是6亿但是常数很小所以只用跑2秒。
指令集优化的bitset与的代码：

#include <emmintrin.h>
friend bool any(const mbit &a,const mbit &b){
	static int res[4];
	memset(res,0,sizeof(res));
	__m128i tmp,*pa=(__m128i*)a.v,*pb=(__m128i*)b.v;
	tmp=_mm_load_si128((__m128i*)res);
	for(int i=0; i<L; i+=2,++pa,++pb){
		tmp=_mm_or_si128(tmp,_mm_and_si128(*pa,*pb));
	}
	_mm_store_si128((__m128i*)res,tmp);
	for(int i=0; i<4; ++i){
		if(res[i]) return 1;
	}
	return 0;
}

中级优化

还是枚举字符x,y。把s中x出现的位置用bitset存起来。
然后考虑t中的某一个y和s’中任意一个x匹配时t的右端点能对应到s哪里:

bitset ans,stat_b;//stat_b为s中x出现的位置集合。
for(int pos: t中字符为y的下标集合) ans|=stat_b<<(|t|-pos)

最后算出来的bitset就是以哪些位置结尾的s’在和t计算时x和y有边。
存下来，离线处理一下就行。
复杂度$n^2/64\times 6$
大概是9亿但是常数更小了，加上数据又水，所以用stl的bitset就能过。。。
但是因为这里bitset的与运算长度必须为|s|，所以优化空间不大，最多除以2（SSE2指令集）。

题解优化

和中级做法一样，枚举x,y，考虑以哪些位置开头的s’在和t计算时x和y有边。
设从p（0-index）开始的s’在和t计算时x和y有边。
那么会有：

$$\sum_ {i=0} ^ {|t|-1}(t[i]==x)\times (s[i+p]==y)>0$$

???这不就是减法卷积吗？fft\fwt\ntt光速切题
复杂度$30\times n\log n$
大概是4000万但是有卷积的超大常数所以跑起来也不快。

外传做法

不考虑优化直接扫一遍的话最后图会呈现出若干个连通块，需要操作的次数是6-连通块数量。
现在考虑一个01状态S表示某一个连通块（1在内部0不在）
那么把s’和t中属于这个连通块的字符改成1，不属于的改成0，一定能保证s’和t完全一样。
但是s’和t完全一样的状态S有可能是多个连通块的集合。
设f[i][j]表示从下标i开始的s’，状态为j时两个按上规则修改后的字符串是否一样。
可以做$2^6$次KMP算出。
然后对每一个f[i]做一次高维前缀和得到g[i]。
当g[i][j]==1时说明从下标i开始的s’和t得到的图中，j恰好是一个连通块，而不是若干个连通块的集合。
统计有多少个这样的j，就可以得到下标i开始的s’的答案。
复杂度$|s|\times 2^6\times 6$，大概也是4000万。