Regular Number(HDU-5972)

给出形如”(0|9|7)(5|6)(2)(4|5)”的正则表达式P, 以及一个之包含数字的文本串T, 输出所有可以匹配的子串.
上面给出的正则表达式的含义是: 一个只有4位的数字, 第一位可以是0,9,7三个中的一个, 第二位可以是5,6中的一个, 第三位只能是2, 第四位可以使4,5中的一个.
数据范围: 正则表达式P所代表的数字位数 \(1 \leq N \leq 1000\), 文本串T的长度 \(0 \leq L \leq 5 \times 10^6\).

解法

暴力匹配

最朴素方法就是暴力匹配, 枚举子串开头的位置, 检查其之后的第i位的数字是否匹配, 如果全部匹配, 则匹配成功, 输出该子串. 检查一位数字是否匹配的复杂度O(1), 总共N位, 子串开头的位置有T-N中情况, 所以总复杂度是\(O(N(L-N))\), 大约\(5 \times 10^9\).

注意到后一个子串其实是前一个子串去掉第一位, 再添加一个新的最后一位, 就是一个左移的操作, 那么就很容易想到使用bitset来检查是否匹配. 因为字符集大小为10, 所以bitset中每10位表示一个数字位. 对于表达式P来说, bitset中每十位代表的是相应数字位可以是几. 对于子串来说, bitset中每十位只有一位是1, 即相应数字位的数字对应的位. 例如题目中的表达式对应的bitset应该是:

每位对应的数字	0123456789 0123456789 0123456789 0123456789
bitset	1000000101 0000011000 0010000000 0000110000

对于四位数字串”1234”, 它对应的bitset应该是:

每位对应的数字	0123456789 0123456789 0123456789 0123456789
bitset	0100000000 0010000000 0001000000 0000100000

这样每次检查匹配时只需要判断子串的bitset和表达式P的bitset相与的结果是否等于子式的bitset. 在检查完后将子式的bitset左移十位, 在把最后十位对应的值置1, 就转化到了新的子串.
因为每十位表示一个数字位, 所以bitset的大小应该是\(10N\). 这样每次检查一个子串复杂度就由\(O(N)\)变为了\(O(\frac{10N}{w})\), 总复杂度为\(O(\frac{10N(L-N)}{w})\), 大约\(1 \times 10^9\).

核心算法:

function BruteForce(string P, string T):
	p = GetBitsetFromPattern(P)
	t = GetBitsetFromText(T[0:N])
	for i = 0; i < L-N; ++i:
		if p & t == t:
			print(T[i:i+N])
		t = t << 10
		t[T[i+N]-'0'] = 1
	return ret

可以看到前面暴力解法的复杂度对于一秒的时限是很可能过不了的, 所以需要更快的解法.

Shift-And

Shift-and是一个很简单却很精妙的算法. 它实现起来很容易, 主要的操作就是其名字所描述的: 移位和与运算. 但是想要想到这样的做法是不容易的.

对于表达式P, 既可以像暴力解法那样用”每个数字位可以是哪些数”来表示, 也可以反过来, 用”每个数字可以在哪些数字位上出现”来表示. 这样可以得到十个N位的bitset: p[0-9], 其中p[i]表示i这个数字可以从出现在N个数字位中的哪些位置. 接下来从文本串的第一位开始考虑, 如果当前位可以出现在莫个被匹配的子串当中, 它可能在子串的哪个位置? 如果当前位出现在子串的第i位, 那么后面的一位必然出现在相应子串的第i+1位. 而每一位的数字是否可以出现在子串的某个位置, 正是由表达式P来约束的. 那么以这种思想来做, 一个新的检查匹配算法就出现了: 检查子串的第i位数字是否可以出现在第i位, 如果每一位的可以, 则匹配成功. 这里的”每一位都可以”就是一个与运算, 所以检查开头在T的第j位的子串是否匹配, 就是:

Match[j] = true
for i = 0; i < N; ++i:
	Match[j] = Match[j] && p[T[j+i]][i]

这样每次使用的是逻辑与运算, 但其实可以通过一个辅助bitset来把它改为位与运算:

tmp = NewBitset()
tmp[0] = 1
for i = 0; i < N; ++i:
	tmp = tmp & p[T[j+i]]
	tmp = tmp << 1
Match[j] = tmp[N]

为什么要使用位运算而不是逻辑运算呢? 因为位运算有一个很重要的性质: 一次位运算可以代替w次逻辑运算. 那么下一个问题就是如何使用位运算的这个性质.
观察逻辑运算求Match[j]和Match[j+1]的算法:

Match[j+1] = p[T[j+1+0]][0] && p[T[j+1+1]][1] && ... && p[T[j+1+N-1]][N-1]
         = p[T[j+1]][0] && p[T[j+2]][1] && ... && p[T[j+N]][N-1]
Match[j] = p[T[j+0]][0] && p[T[j+1]][1] && ... && p[T[j+N-1]][N-1]

可以发现在求Match[j+1]时, 除了最后一次运算外, 前面的每一次运算使用的都是计算Match[j]时的前一位. 那么如果能够让这些运算和计算Match[j]时的运算同时进行, 就可以减少大量的计算了, 而位运算正好可以做到这一点.
在求Match[j]的位运算版本中, 在计算p[T[j+i]]时, 用到的只有第i位, 而Match[j+1]在计算p[T[j+i]]时用到的时第i-1位. 两者相互之间不影响, 所以就可以用位运算来并行处理. 显然两个以上的Match也可以并行计算, 于是可以有下面的解法:

function ShiftAnd(string P, string T):
	tmp = NewBitset();
	for i = 0; i < 10; ++i:
		p[i] = GetBitsetFromPattern2(P, i)
	for i = 0; i < L; ++i:
		tmp = tmp << 1
		tmp[0] = 1
		tmp = tmp & p[T[i]-'0']
		if tmp[N-1] == 1:
			printf(T[i:i+N])

其中tmp为一个N位的bitset, 这样可以算出该算法复杂度为\(O(\frac{LN}{w})\), 大约\(1 \times 10^8\).

C++代码

#include <bitset>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long LL;

const int MAXN = 1000;
const int INF = 0x3f3f3f3f;
const LL MOL = 100000073;

char str[5000010];

bitset<1000> p[10], ans;

int main() {
	int n, a, k;
	while (-1 != scanf("%d", &n)) {
		for (int i = 0; i < 10; ++i) p[i].reset();
		ans.reset();
		for (int i = 0; i < n; ++i) {
			scanf("%d", &a);
			for (int j = 0; j < a; ++j) {
				scanf("%d", &k);
				p[k].set(i);
			}
		}
		scanf("%s", str);
		int l = strlen(str);
		for (int i = 0; i < l; ++i) {
			ans <<= 1;
			ans.set(0);
			ans &= p[str[i]-'0'];
			if (ans[n-1] == 1) {
				char tmp = str[i+1];
				str[i+1] = '\0';
				puts(str+i-n+1);
				str[i+1] = tmp;
			}
		}
	}
	return 0;
}