BM算法模板

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了BM算法模板，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2708字，纯文字阅读大概需要4分钟。

内容图文

有一个序列\(a[1..n]\)，求最短的\(f[1..len]\)，使得：
\(\forall i>len,\sum_{j=1}^{len} f[j]*a[i-j]=a[i]\)

假设已经求出了\(a[1..i-1]\)的最短递推式\(f\)

设\(?=a[i]-\sum_{j=1}^{len} f[j]*a[i-j]\)

当\(?=0\)时，显然\(f\)可以作为\(a[1..i]\)的递推式，continue

当\(?≠0\)时，我们想要找到一个递推式\(g\)，使得\(g\)代入\(i\)是1，\(g\)代入\(1..i-1\)是0，这样：
新的\(f'=f+g*?\)

考虑之前有一次失配，递推式\(h0\)在\(fail\)处失配了，当时的\(?\)是\(?'\)。
令\(h=h0*x^{i-fail}\)，不难发现，
1.\(h代入i的值=h0代入fail\)的值，
2.\(h代入i-j(j>0)的值=h0代入fail-j的值=0\)

那么再使\(h[i]=-h[i],h[i-fail]++\)

则\(h\)代入\(i\)的值=\(?'\)，代入\(i-j(j>0)\)的值\(=0\)

那么\(f'=f+h*?/?'\)

\(h\)的长度是\(i-fail+|h0|\)，所以动态维护\(i-fail\)最小的失配的\(f\)作为\(h0\)即可

实现需要注意的细节：
1.当第一次遇到一个≠0的数时，len才赋值1，需特判
2.记得更新fail
3.滚动优化空间，实现见代码

---

模板题：https://www.luogu.com.cn/problem/P5487
Code：

#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i <  _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("\n")
using namespace std;

const int mo = 998244353;

ll ksm(ll x, ll y) {
	ll s = 1;
	for(; y; y /= 2, x = x * x % mo)
		if(y & 1) s = s * x % mo;
	return s;
}

const int N = 10005;

namespace sub1 {
	ll f[3][N], dta[3];
	int len[3], fail[3];
	void cp(int x, int y) {
		len[y] = len[x]; fail[y] = fail[x]; dta[y] = dta[x];
		fo(i, 1, len[x]) f[y][i] = f[x][i];
	}
	void build(ll *a, int n) {
		fo(i, 0, n) {
			ll d = a[i];
			fo(j, 1, len[0]) d = (d - f[0][j] * a[i - j]) % mo;
			dta[0] = d;
			if(!d) continue;
			fail[0] = i;
			if(!len[0]) {
				cp(0, 1); len[0] = 1;
				continue;
			}
			cp(0, 2);
			ll c = dta[0] * ksm(dta[1], mo - 2) % mo;
			int st = i - fail[1]; len[0] = max(len[0], st + len[1]);
			f[0][st] = (f[0][st] + c) % mo;
			fo(j, 1, len[1]) f[0][st + j] = (f[0][st + j] - c * f[1][j]) % mo;
			if(len[2] - fail[2] < len[1] - fail[1]) cp(2, 1);
		}
	}
}

int n, m; ll a[N];

ll f[N]; int len;

ll x[N], s[N], c[N];

void cheng(ll *a, ll *b) {
	fo(i, 0, 2 * len) c[i] = 0;
	fo(i, 0, len) fo(j, 0, len)
		c[i + j ] = (c[i + j] + a[i] * b[j]) % mo;
	fo(i, 0, 2 * len) a[i] = c[i];
	fd(i, 2 * len, len + 1)	{
		ll v = a[i]; int st = i - (len + 1);
		fo(j, 1, len) a[st + j] = (a[st + j] - v * f[j]) % mo;
	}
}

int main() {
	scanf("%d %d", &n, &m);
	fo(i, 1, n) scanf("%lld", &a[i]);
	sub1 :: build(a, n);
	
	len = sub1 :: len[0];
	fo(i, 1, len) f[i] = sub1 :: f[0][i];
	
	fo(i, 1, len) {
		f[i] = (f[i] % mo + mo) % mo;
		pp("%lld ", f[i]);
	}
	hh;
	
	reverse(f + 1, f + len + 1);
	fo(i, 1, len) f[i] = -f[i]; f[len + 1] = 1;
	
	x[1] = 1; s[0] = 1;
	for(m ++; m; m /= 2, cheng(x, x)) 
		if(m & 1) cheng(s, x);
		
	ll ans = 0;
	fo(i, 1, len) ans = (ans + s[i] * a[i]) % mo;
	pp("%lld\n", (ans % mo + mo) % mo);
}

内容总结

以上是互联网集市为您收集整理的BM算法模板全部内容，希望文章能够帮你解决BM算法模板所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---