【洛谷P4173】残缺的字符串

题目大意：给定一个文本串和一个模板串，串中含有通配符，求文本串中有多少个位置可以与文本串完全匹配。

题解：利用卷积求解字符串匹配问题。

通配符字符串匹配的数值表示为 $$\sum\limits_{i = 0}^{m - 1}(a[i] - b[i + k])^2 a[i]b[i + k]=0$$。直接展开之后计算三个卷积即可。

需要注意的是：并不是所有 a[i] b[i + k] 均为循环卷积，是否需要倍增取决于是否成环。

代码如下

#include <bits/stdc++.h>

using namespace std;

typedef complex<double> cp;

const double eps = 1e-8;

const double pi = acos(-1);

int main() {

	ios::sync_with_stdio(false);

	cin.tie(0);

	int n, m;

	cin >> m >> n;

	string s, t;

	cin >> t >> s;

	int tot = 1, bit = 0;

	while (tot <= n + m) {

		tot <<= 1;

		++bit;

	}

	vector<int> rev(tot);

	for (int i = 0; i < tot; i++) {

		rev[i] = rev[i >> 1] >> 1 | (i & 1) << bit - 1;

	}

	vector<cp> a1(tot), a2(tot), a3(tot), b1(tot), b2(tot), b3(tot);

	auto work = [](char ch) {

		if (ch == '*') {

			return 0;

		} else {

			return ch - 'a' + 1;

		}

	};

	for (int i = 0; i < m; i++) {

		int x = work(t[i]);

		a1[m - 1 - i] = x;

		a2[m - 1 - i] = x * x;

		a3[m - 1 - i] = x * x * x;

	}

	for (int i = 0; i < n; i++) {

		int x = work(s[i]);

		b1[i] = x;

		b2[i] = x * x;

		b3[i] = x * x * x;

	}

	auto fft = [=](vector<cp> &v, int opt) {

		for (int i = 0; i < tot; i++) {

			if (i < rev[i]) {

				swap(v[i], v[rev[i]]);

			}

		}

		for (int mid = 1; mid < tot; mid <<= 1) {

			cp wn(cos(pi / mid), opt * sin(pi / mid));

			for (int j = 0; j < tot; j += mid << 1) {

				cp w(1, 0);

				for (int k = 0; k < mid; k++) {

					cp x = v[j + k], y = w * v[j + mid + k];

					v[j + k] = x + y, v[j + mid + k] = x - y;

					w *= wn;

				}

			}

		}

		if (opt == -1) {

			for (int i = 0; i < tot; i++) {

				v[i].real(round(v[i].real() / tot));

			}

		}

	};

	auto calc = [=](vector<cp> &a, vector<cp> &b) {

		fft(a, 1), fft(b, 1);

		for (int i = 0; i < tot; i++) {

			a[i] *= b[i];

		}

		fft(a, -1);

	};

	calc(a3, b1), calc(a2, b2), calc(a1, b3);

	int ans = 0;

	vector<int> pos;

	for (int k = 0; k < n - m + 1; k++) {

		double ret = a3[m + k - 1].real() - 2 * a2[m + k - 1].real() + a1[m + k - 1].real();

		if (fabs(ret) < eps) {

			++ans;

			pos.push_back(k + 1);

		}

	}

	cout << ans << endl;

	for (auto p : pos) {

		cout << p << " ";

	}

	return 0;

}

巴特西

【洛谷P4173】残缺的字符串

最新文章

热门文章