字符串笔记

字符串知识点

字符串基本概念

定义

Border

字符串 \(S\) 的同长度前缀和后缀完全相同, \(Prefix[i] = Suffix[i] <=> S[1,p] == S[|S|-p+1, |S|]\) ，则称为 \(Border\) ，字符串本身可以是自己的 \(Border\) 根据情况判断。

  • \(Prefix[i]\) 的 Border 长度减 \(1\) 是 \(Prefix[i - 1]\) 的 Border 长度，反之不一定成立, 需要检验后一个字符是否相等。

周期

  • 对于字符串 \(S\) 和正整数 \(p\) ,如果有 \(S[i] = S[i - p]\) ，对于 \(p < i \leq |S|\) 成立，则 \(p\) 为字符串的一个周期。
  • 当然，\(p=|S|\) 一定是 \(S\) 的周期

循环节

  • \(p\) 是字符串 \(S\) 的周期，满足 \(p \;|\; |S|\) ，则 \(p\) 是 \(S\) 的一个循环节。
  • 当然，\(p = |S|\) 是 \(S\) 的循环节

性质

  • \(p\) 是 \(S\) 的周期等价于 \(|S| - p\) 是 \(S\) 的 Border。
    • 即字符串周期性质等价于 Border 性质，注意 Border不具有二分性。
  • Border 具有传递性，即 Border 的 Border 也是字符串的 Border。
    • 即求字符串的所有 Border 等价于求所有前缀的最大Border。

KMP

Next数组

  • \(ne[i] = Prefix[i]\) 的非平凡最大 Border，在前缀里找 Border。
  • \(ne[1] = 0\)
  • 求 \(Prefix[i]\) 的所有长度大于 1 的 Border。去掉最后一个字母就变成 \(Prefix[i - 1]\) 的Border
    • 故求 \(ne[i]\) 的时候，遍历 \(Prefix[i - 1]\) 的所有 Border，即 \(ne[i - 1], ne[ne[i - 1]], ... , 0\)。检查最后一个字符是否等于 \(S[i]\)

Border树

对于字符串 \(S\)， \(n = |S|\)，它的 Border 树 （next 树） 共有 \(n+1\) 个节点：\(0, 1, 2, 3,..,n\)， \(0\) 是这颗有向树的根。对于其他节点父节点为 \(ne[i]\)

性质

  • 每个前缀 \(Prefix[i]\) 的所有 Border ，就是节点 \(i\) 到根的链。
  • 哪些前缀有长度为 \(x\) 的 Border，等价于 \(x\) 的子树
  • 求两个前缀的公共 Border，等价于求两个节点的 \(LCA\)

字符串哈希

Trie

字典：一个字符串的集合
字典串：在字典里的串

01-Trie

题目多于普通 Trie，也更难。
异或两种做法：

  1. 线性基
  2. 01-Trie

可持久化 Trie

可持久化思想：将修改操作在新的节点，不对原节点修改

AC自动机

Manacher

字符串好题

KMP

差分 + KMP

题意

有一个长度为 \(n\) 的数列 \(A\) ，一个长度为 \(m\) 的数列 \(B\) ，现在询问 \(A\) 中有多少个长度为 \(m\) 的连续子序列 \(A'\)，
满足 \((a_1'+b_1)\%k = (a_2'+b_2)\%k = ... = (a_m' + b_m)\%k\)。

思路

  • 化简式子，利用差分得 \((a_1' - a_2') \% k = (b_2 - b_1) \% k \dots (a_{m-1}' - a_m') \% k = (b_m - b_{m-1}) \% k\)
  • 差分后序列长度均减 \(1\) ，首尾不能相连，然后进行 KMP 算法
  • 注意模意义下相同需要相减 \(\% k ==0\)

Solution

#include
typedef long long ll;
typedef std::pair PII;
typedef std::pair PLL;
#define x first
#define y second
#define pb push_back
#define mkp make_pair
#define endl "\n"
using namespace std;
const int N = 2e5 + 10;
int ta[N], tb[N], n, m, k, a[N], b[N];
int ne[N], ans;

void get_ne(int* s){
	int len = m;
	ne[1] = ans = 0;
	for(int i = 2, j = 0; i <= len; i++){
		while(j && (s[j + 1] - s[i]) % k) j = ne[j];
		if((s[i] - s[j + 1]) % k == 0) j++;
		ne[i] = j;
	}
}

void Match(int s[], int p[]){		
	int lens = n, lenp = m;
	for(int i = 1, j = 0; i <= lens; i++){
		while(j && (s[i] - p[j + 1]) % k ) j = ne[j];
		if((s[i] - p[j + 1]) % k == 0) j++;
		if(j == lenp){
			ans ++;
			j = ne[j];
		}
	}
}

int sub(int x, int y){
	return (x - y + k) % k;
}

int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	while(T--){
		cin >> n >> m >> k;
		for(int i = 1; i <= n; i++) 
			cin >> ta[i];
		for(int i = 1; i <= m; i++) 
			cin >> tb[i];
		for(int i = 1; i <= n - 1; i++){
			a[i] = sub(ta[i], ta[i % n + 1]);
		}
		for(int i = 1; i <= m - 1; i++){
			b[i] = sub(tb[i % m + 1], tb[i]);
		}
		get_ne(b);
		n--, m--;
		Match(a, b);
		cout << ans << endl;
	}
    return 0;
}

KMP 求矩阵最小公共循环周期 + 单调队列

题意

给你一个 \(n*m\) 的矩阵，每个格子有自己的颜色和权值，现在要你选择一个子矩阵，假设子矩阵的大小是 \(p*q\) 的，
子矩阵选择的条件是，将子矩阵无限的平移复制粘贴，原来的 \(n*m\) 的矩阵是复制粘贴之后矩阵的子矩阵，
选择子矩阵有一个花费，花费是原矩阵所有的大小为 \(p*q\) 的子矩阵中选择一个最大值 \(x\) ，花费就是 \(x*(p + 1)*(q + 1)\) 。

数据范围
\(n*m<=1e6\)。

思路

Solution

#include
typedef long long ll;
#define endl "\n"
using namespace std;
const int N = 1e6 + 100;
string s[N];
int mp[N], q[N], n, m, ne[N];

void get_ne(string s){
	int len = s.size() - 1;
	ne[1] = 0;
	for(int i = 2, j = 0; i <= len; i++){
		while(j && s[j + 1] != s[i]) j = ne[j];
		if(s[i] == s[j + 1]) j++;
		ne[i] = j;
	}
}

int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> s[i];
		s[i] = " " + s[i];
	}
	vector> c(n + 1, vector(m + 1, 0));
	vector> val(n + 1, vector(m + 1, 0));
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cin >> c[i][j];
	int x = n, y = m;
	for(int i = 1; i <= n; i++){
		get_ne(s[i]);
		int t = m;
		while(ne[t]){
			mp[m - ne[t]] ++;
			if(mp[m - ne[t]] == n){
				y = min(m - ne[t], y);
			}
			t = ne[t];
		}
	}
	memset(mp, 0, sizeof mp);
	for(int i = 1; i <= m; i++){
		string t(n + 1, 0);
		for(int j = 1; j <= n; j++)
			t[j] = s[j][i];
		get_ne(t);
		int tmp = n;
		while(ne[tmp]){
			mp[n - ne[tmp]] ++;
			if(mp[n - ne[tmp]] == m)
				x = min(n - ne[tmp], x);
			tmp = ne[tmp];
		}
	}
	for(int i = 1; i <= n; i++){
		int hh = 0, tt = -1;
		for(int j = 1; j < y; j++){
			while(hh <= tt && c[i][q[tt]] <= c[i][j]) tt--;
			q[++tt] = j;
		}
		for(int j = y; j <= m; j++){
			if(hh <= tt && j - q[hh] >= y) hh++;
			while(hh <= tt && c[i][q[tt]] <= c[i][j]) tt--;
			q[++tt] = j; 
			val[i][j] = c[i][q[hh]];
		}
	}
	ll ans = 2e9;
	for(int i = y; i <= m; i++){
		int hh = 0, tt = -1;
		for(int j = 1; j < x; j++){
			while(hh <= tt && val[q[tt]][i] <= val[j][i]) tt--;
			q[++tt] = j;
		}
		for(int j = x; j <= n; j++){
			if(hh <= tt && j - q[hh] >= x) hh++;
			while(hh <= tt && val[q[tt]][i] <= val[j][i]) tt--;
			q[++tt] = j;
			ans = min(ans, 1ll * val[q[hh]][i]);
		}
	}
	cout << 1ll * (x + 1) * (y + 1) * ans << endl;
    return 0;
}

Trie

Trie + 拓扑排序判环

题意

给定 \(n\) 个字符串，互不相等，你可以任意指定字符之间的大小关系（即重定义字典序），求有多少个串可能成为字典序最小的串，并输出它们

思路

  • 首先建立所有字典串的 Trie 树，然后考虑什么时候不能字典序最小
  • 存在一个字典串是另一个字典串的前缀，那么后者不可能字典序最小
  • 寻找该字典串时，节点的其他路径所达到的节点字符字典序必须大于目标路径所到达节点
  • 前缀可对路径节点标记判断得解，字典序的大小关系可以建立DAG，再用拓扑图判环，有环则不合法，并注意并查集并不能实现DAG判环

Solution

#include
typedef long long ll;
typedef std::pair PII;
typedef std::pair PLL;
#define x first
#define y second
#define pb push_back
#define mkp make_pair
#define endl "\n"
using namespace std;
const int N = 3e5 + 10;
int n, son[N][26], cnt[N], g[26][26], idx, indeg[26];
vector ans;

void insert(string s){
	int p = 0;
	for(auto c: s){
		int u = c - 'a';
		if(!son[p][u]) son[p][u] = ++idx;
		p = son[p][u];	
	}
	cnt[p]++;
}

bool check(){
	queue q;
	for(int i = 0; i < 26; i++){
		if(!indeg[i])
			q.push(i);
	}
	while(q.size()){
		int t = q.front();
		q.pop();
		for(int i = 0; i < 26; i++){
			if(g[t][i]){
				indeg[i] -= g[t][i];
				g[t][i] = 0;
				if(!indeg[i])
					q.push(i);
			}
		}
	}
	for(int i = 0; i < 26; i++)
		if(indeg[i])
			return false;
	return true;
}

bool query(string s){
	int p = 0;
	memset(g, 0, sizeof g);
	memset(indeg, 0, sizeof indeg);
	for(auto c: s){
		int u = c - 'a';
		if(cnt[p]) return false;
		for(int i = 0; i < 26; i++){
			if(son[p][i] && i != u){
				g[u][i] ++;
				indeg[i]++;
			}
		}
		p = son[p][u];
	}
	bool fl = check();
	return fl;
}


int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	vector v;
	for(int i = 0; i < n; i++){
		string s;
		cin >> s;
		insert(s);
		v.pb(s);
	}
	for(auto s: v){
		if(query(s)) ans.pb(s);
	}
	cout << ans.size() << endl;
	for(auto t: ans)
		cout << t << endl;
    return 0;
}

AC自动机

模拟 + 字符集特殊处理

题意

模拟题

思路

  • 根据题意模拟，然后跑一遍AC自动机
  • 一定注意 \(8\) 个 bit 转换成整数，可能出现比 \(128\) 大或者需要对 \0 特殊处理，均转换为 int 存储。

Solution

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
typedef long long ll;
typedef std::pair PII;
typedef std::pair PLL;
#define x first
#define y second
#define pb push_back
#define endl "\n"
using namespace std;
int n, m;

string int2bin(int x){
	string res;
	for(int i = 5; i >= 0; i--)
		res += char(((x >> i) & 1) + '0');
	return res;
}

string char2bin(char c){
	if(c >= 'A' && c <= 'Z') return int2bin(c - 'A');
	if(c >= 'a' && c <= 'z') return int2bin(26 + c - 'a');
	if(c >= '0' && c <= '9') return int2bin(52 + c - '0');
	if(c == '+') return int2bin(62);
	if(c == '/') return int2bin(63);
	return "";
}

const int N = 520, M = 520 * 64, S = 256;
bool vis[M];
int cnt[M], tr[M][S], idx, fail[M];

void insert(vector s){
	int p = 0;
	for(int i = 0; i < s.size(); i++){
		int c = s[i];
		if(!tr[p][c]) tr[p][c] = ++idx;
		p = tr[p][c];
	}
	cnt[p]++;
}

void build(){
	queue q;
	for(int i = 0; i < S; i++)
		if(tr[0][i])
			q.push(tr[0][i]);
	while(q.size()){
		auto u = q.front();
		q.pop();
		for(int i = 0; i < S; i++){
			if(tr[u][i])
				fail[tr[u][i]] = tr[fail[u]][i], q.push(tr[u][i]);
			else
				tr[u][i] = tr[fail[u]][i];
		}
	}
}

int query(vector s){
	memset(vis, 0, sizeof vis);
	int u = 0, res = 0;
	for(int i = 0; i < s.size(); i++){
		u = tr[u][s[i] - 0];
		for(int j = u; j && !vis[j]; j = fail[j]){
			res += cnt[j], vis[j] = true;
		}
	}
	return res;
}

void init(){
	idx = 0;
	memset(tr, 0, sizeof tr);
	memset(fail, 0, sizeof fail);
	memset(cnt, 0, sizeof cnt);
}

string str2bin(string ori){
	int t = 0;
	string res = "";
	for(int j = 0; j < ori.size(); j++){
		char c = ori[j];
		if(c != '='){
			res += char2bin(c);
		}
		else
			t++;
	}
	res = res.substr(0, res.size() - 2 * t);
	return res;
}

vector bin2asc(string ori){
	vector s;
	for(int i = 0; i < ori.size(); i += 8){
		int res = 0;
		for(int j = i; j < i + 8; j++){
			char c = ori[j];
			int d = j - i;
			if(c == '1')
				res += 1 << (7 - d);
		}
		s.pb(res);
	}
	return s;
}

int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	bool fl = false;
	while(cin >> n){
		init();	
		for(int i = 0; i < n; i++){
			string s;
			cin >> s;
			s = str2bin(s);
			vector res = bin2asc(s);
			insert(res);
		}
		build();
		cin >> m;
		while(m--){
			string s;
			cin >> s;
			s = str2bin(s);
			vector res = bin2asc(s);
			cout << query(res) << endl;
		}
		cout << endl;
	}
    return 0;
}

AC自动机DAG + 矩阵快速幂

题意

给定 \(m\) 个字符串（仅含有 \(A T C G\) ，长度不超过 \(10\) ），和正整数 \(n\) ,问有多少种仅包含 \(A T C G\) 的长度为 \(n\) 的字符串，满足不包含这 \(m\) 个字符串中的任意一个作为子串。

数据范围
\(1\leq m \leq 10\)
\(1\leq n \leq 2e9\)

思路

  • 利用建立AC自动机后可以得到一个有向图，点权（或边权）是字符集，将问题转化。
  • 转化后问题等价于，在有向图上找出一条从 \(0\) 出发经过 \(n\) 条边的合法路径的方案数，合法路径上不含病毒，即不包含 \(Fail\) 树上所有病毒点的子树节点。
  • 经过上述转化后如果你对矩阵快速幂熟悉的话，会发现这是矩阵快速幂的一个经典问题, 最后套用矩阵快速幂，统计 \(0\) 到所有点的方案总数即可。
    • 定义 \(M[i][j]\) 为从 \(i\) 到 \(j\) 的路径数，那么经过两条边的方案数就是 \(M[i][j]^2\)。
    • 当然，经过 \(n\) 条边的方案数就是 \(M[i][j]^n\)
  • 矩阵记得开 long long

Solution

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
typedef long long ll;
typedef std::pair PII;
typedef std::pair PLL;
#define x first
#define y second
#define pb push_back
#define mkp make_pair
#define endl "\n"
using namespace std;
const int N = 101, M = 15 * N, S = 4, mod = 1e5;
int tr[M][S], idx, fail[M];
ll n, m;
bool st[M];

int get(char c){
	if(c == 'A')
		return 0;
	if(c == 'T')
		return 1;
	if(c == 'C')
		return 2;
	return 3;
}

void insert(string s){
	int p = 0;
	for(int i = 0; i < s.size(); i++){
		int c = get(s[i]);
		if(!tr[p][c]) tr[p][c] = ++idx;
		p = tr[p][c];
	}
	st[p] = true;
}

void build(){
	queue q;
	for(int i = 0; i < S; i++)
		if(tr[0][i])
			q.push(tr[0][i]);
	while(q.size()){
		int u = q.front();
		q.pop();
		if(st[fail[u]]) 
			st[u] = true;
		for(int i = 0; i < S; i++){
			if(tr[u][i])
				fail[tr[u][i]] = tr[fail[u]][i], q.push(tr[u][i]);
			else
				tr[u][i] = tr[fail[u]][i];
		}
	}
}

template  struct Mat {
	int len;
	Mat() { memset(data, 0, sizeof(data)); len = idx + 1; }

	T *operator[](int i) { return data[i]; }

	const T *operator[](int i) const { return data[i]; }

	T add(T a, T b){
		return (a + b) % mod;
	}

	Mat &operator += (const Mat &o) {
		for (int i = 0; i < len; ++i) 
			for (int j = 0; j < len; ++j) 
				data[i][j] = add(data[i][j], o[i][j]);
		return *this;
	}

	Mat operator + (const Mat &o) const {
		return Mat(*this) += o;
	}

	Mat &operator -= (const Mat &o) {
		for (int i = 0; i < len; ++i) 
			for (int j = 0; j < len; ++j) 
				data[i][j] = add(data[i][j], -o[i][j]);
		return *this;
	}

	Mat operator-(const Mat &o) const {
		return Mat(*this) -= o;
	}

	Mat operator*(const Mat &o) const {
		static T buffer[N];
		Mat result;
		for (int j = 0; j < len; ++j) {
			for (int i = 0; i < len; ++i) 
				buffer[i] = o[i][j];
			for (int i = 0; i < len; ++i) 
				for (int k = 0; k < len; ++k) 
					result[i][j] += (data[i][k] * buffer[k]) % mod;
		}
		return result;
	}

	Mat power(unsigned long long k) const {
		Mat res;
		for (int i = 0; i < len; ++i) 
			res[i][i] = T{1};
		Mat a = *this;
		while (k) {
			if (k & 1ll) 
				res = res * a;
			a = a * a;
			k >>= 1ll;
		}
		return res;
	}

	private:
		T data[N][N];
};



template 
void get_mat(Mat& g){
	for(int u = 0; u <= idx; u++){
		for(int j = 0; j < 4; j++){
			if(!st[u] && !st[tr[u][j]])
				g[u][tr[u][j]] ++;
		}
	}
}


int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> m >> n;
	for(int i = 0; i < m; i++){
		string s;
		cin >> s;
		insert(s);
	}
	build();
	Mat ans;
	get_mat(ans);
	ans = ans.power(n);
	ll res = 0;
	for(int i = 0; i <= idx; i++){
		res = (res + ans[0][i]) % mod;
	}
	cout << res % mod << endl;
    return 0;
}

AC自动机 + 矩阵快速幂（矩阵分块，矩阵快速幂求解等比数列）

题意

求包含至少一个字典串长度至多为 \(n\) 的字符串个数，大体与上题类似

思路

  • 与上体思路相同，但此题求长度小于等于 \(n\) 的所有方案，考虑取补集，总方案数 - 不包含任意字典串的字符串个数 = 答案
  • 显然总方案数为 \(26 + 26^2 + 26^3 +...+ 26^n\) ，遗憾的是这里最好不用等比数列来解，考虑矩阵快速幂

    • 构造矩阵 \(A = \begin{bmatrix} 26 & 1 \\ 0 & 1 \\ \end{bmatrix}\)

    • 则 \(A^n = \begin{bmatrix} 26^n & 26^{n - 1} + 26^{n - 2} + \cdots + 1\\ 0 & 1 \end{bmatrix}\)

    • 取第一行元素和为 \(A^n + A^{n - 1} + A^{n - 2} + \cdots + 1\) ，减 \(1\) 便是所求总方案数

  • 对于不包含任意字符串的个数，由上一题可知，长度固定的情况下是好求的，其实长度小于 \(n\) 的方案数就是 \(G + G^2 +\cdots + G^n\) ，矩阵的幂次和，那么如何求解矩阵幂次和呢？
    • 神奇的是，我们只需要将上述矩阵 \(A\) 中 \(26\) 替换为矩阵 \(G\) 即可，其中 \(1\) 替换为单位阵
    • 最后遍历整个矩阵 \(G[0][i]\) 的和减 \(1\) 就是不包含任意字典串的字符串个数。
  • 小细节，对 \(2^{64}\) 取模，只需要将数据类型改为 unsigned long long。

Solution

#include
typedef long long ll;
typedef std::pair PII;
typedef std::pair PLL;
typedef unsigned long long ull;
#define x first
#define y second
#define pb push_back
#define mkp make_pair
#define endl "\n"
using namespace std;

const int M = 31, S = 26;

int tr[M][S], idx, fail[M];
bool st[M];
int n, m;

void insert(string s){
	int p = 0;
	for(int i = 0; i < s.size(); i++){
		int c = s[i] - 'a';
		if(!tr[p][c]) tr[p][c] = ++idx;
		p = tr[p][c];
	}
	st[p] = true;
}

void build(){
	queue q;
	for(int i = 0; i < S; i++)
		if(tr[0][i])
			q.push(tr[0][i]);
	while(q.size()){
		auto u = q.front();
		q.pop();
		if(st[fail[u]]) st[u] = true;
		for(int i = 0; i < S; i++){
			if(tr[u][i])
				fail[tr[u][i]] = tr[fail[u]][i], q.push(tr[u][i]);
			else
				tr[u][i] = tr[fail[u]][i];
		}
	}
}

template  struct Mat {
	int len;
	Mat() { memset(data, 0, sizeof(data)); len = N; }

	T *operator[](int i) { return data[i]; }

	const T *operator[](int i) const { return data[i]; }

	T add(T a, T b){
		return a + b;
	}

	Mat &operator += (const Mat &o) {
		for (int i = 0; i < len; ++i) 
			for (int j = 0; j < len; ++j) 
				data[i][j] = add(data[i][j], o[i][j]);
		return *this;
	}

	Mat operator + (const Mat &o) const {
		return Mat(*this) += o;
	}

	Mat &operator -= (const Mat &o) {
		for (int i = 0; i < len; ++i) 
			for (int j = 0; j < len; ++j) 
				data[i][j] = add(data[i][j], -o[i][j]);
		return *this;
	}

	Mat operator-(const Mat &o) const {
		return Mat(*this) -= o;
	}

	Mat operator*(const Mat &o) const {
		static T buffer[N];
		Mat result;
		for (int j = 0; j < len; ++j) {
			for (int i = 0; i < len; ++i) 
				buffer[i] = o[i][j];
			for (int i = 0; i < len; ++i) 
				for (int k = 0; k < len; ++k) 
					result[i][j] += (data[i][k] * buffer[k]);
		}
		return result;
	}

	Mat power(unsigned long long k) const {
		Mat res;
		for (int i = 0; i < len; ++i) 
			res[i][i] = T{1};
		Mat a = *this;
		while (k) {
			if (k & 1ll) 
				res = res * a;
			a = a * a;
			k >>= 1ll;
		}
		return res;
	}

	private:
		T data[N][N];
};

template 
Mat get_mat(){
	Mat g;
	for(int i = 0; i <= idx; i++){
		for(int j = 0; j < 26; j++){
			if(!st[i] && !st[tr[i][j]])
				g[i][tr[i][j]] ++;
		}
	}
	return g;
}

void init(){
	idx = 0;
	memset(tr, 0, sizeof tr);
	memset(fail, 0, sizeof fail);
	memset(st, 0, sizeof st);
}

ull qmi(ull a, ull k){
	ull res = 1;
	while(k){
		if(k & 1ull)
			res = res * a;
		a = a * a;
		k >>= 1ull;
	}
	return res;
}

int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	while(cin >> m >> n){
		init();
		for(int i = 0; i < m; i++){
			string s;
			cin >> s;
			insert(s);
		}
		build();
		auto res = get_mat();
		Mat a;
		int len = idx + 1;
		for(int i = 0; i < len; i++){
			for(int j = 0; j < len; j++){
				a[i][j] = res[i][j];
			}
			a[i][i + len] = 1;
		}
		for(int i = len; i < 2 * len; i++){
			for(int j = 0; j < len; j++){
				a[i][j] = 0;
			}
			a[i][i] = 1;
		}
		a = a.power(n);
		ull ans = 0;
		for(int i = 0; i < 2 * len; i++){
			ans += a[0][i];
		}
		ans--;
		Mat b;
		b[0][0] = 26, b[0][1] = 1, b[1][1] = 1;
		b = b.power(n);
		ull sum = b[0][0] + b[0][1] - 1;
		cout << sum - ans << endl;
	}
    return 0;
}

AC自动机 + 状态压缩DP

题意

给了 \(m\) 个字典串，问你能构造多少种长度为 \(n\) 的字符串，满足至少包含 \(k\) 个不同的字典串。

数据范围

\(1\leq n\leq 25, 1 \leq m \leq 10, 1\leq k\leq10\)
答案对 \(20090717\) 取模

思路

  • DP不难想到，个人做的难点是想到使用状压 DP 在 Trie 图上跑。
  • \(f[i][j][s]\) 表示当前长度为 \(i\)，停留在 \(j\) 点，经过的字典串状态为 \(s\) 的方案数。
  • \(f[i][v][nxt] = \Sigma f[i - 1][u][s | st[v]]\)，\(u\) 是 \(v\) 父节点，若 (st[v] >> id) & 1 == 1 表明在节点 \(v\) 包含了编号为 id 的字典串
  • 统计答案，在各点所有状态上加和，判断状态经过字典串个数是否大于 \(k\) 即可。

Solution

#include
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair PII;
typedef std::pair PLL;
#define x first
#define y second
#define pb push_back
#define mkp make_pair
#define endl "\n"
using namespace std;
const int M = 110, S = 26, mod = 20090717;

int tr[M][S], idx, fail[M];
int st[M];
ll f[26][M][1 << 10];

void insert(string s, int x){
	int p = 0;
	for(int i = 0; i < s.size(); i++){
		int c = s[i] - 'a';
		if(!tr[p][c]) tr[p][c] = ++idx;
		p = tr[p][c];
	}
	st[p] |= 1 << x;
}

void build(){
	queue q;
	for(int i = 0; i < S; i++)
		if(tr[0][i])
			q.push(tr[0][i]);
	while(q.size()){
		auto u = q.front();
		q.pop();
		st[u] |= st[fail[u]];
		for(int i = 0; i < S; i++){
			if(tr[u][i])
				fail[tr[u][i]] = tr[fail[u]][i], q.push(tr[u][i]);
			else
				tr[u][i] = tr[fail[u]][i];
		}
	}
}

void init(){
	idx = 0;
	memset(tr, 0, sizeof tr);
	memset(st, 0, sizeof st);
	memset(fail, 0, sizeof fail);
	memset(f, 0, sizeof f);
}


int add(int a, int b){
	return (a + b) % mod;
}

int num[1 << 10];

int get(int x){
	int res = 0;
	while(x){
		if(x & 1) res++;
		x >>= 1;
	}
	return res;
}

int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n, m, k;
	for(int i = 0; i < 1 << 10; i++){
		num[i] = get(i);
	}
	while(cin >> n >> m >> k, n || m || k){
		init();
		for(int i = 0; i < m; i++){
			string s;
			cin >> s;
			insert(s, i);
		}
		build();
		f[0][0][0] = 1;
		for(int i = 1; i <= n; i++)
			for(int u = 0; u <= idx; u++)
				for(int s = 0; s < 1 << m; s ++){
					if(f[i - 1][u][s])
						for(int t = 0; t < S;t ++){
							int v = tr[u][t];
							int nxt = s | st[v];
							f[i][v][nxt] = add(f[i][v][nxt], f[i - 1][u][s]);
						}
				}
		ll ans = 0;
		for(int i = 0; i <= idx; i++){
			for(int j = 0; j < 1 << m; j++){
				if(num[j] >= k)
					ans = add(ans, f[n][i][j]);
			}
		}
		cout << ans << endl;
	}
    return 0;
}
`
算法字符串

相关

如何实现LRU（最近最少使用）缓存淘汰算法？

js 正则匹配 两个字符串之间，某个字符串之前（之后）的内容

2021.11.16（各排序算法对比）

react dom移动算法

算法第四章上机实验报告

算法第二章实践报告

【莫队算法】

大爽Python入门教程 1-2 数与字符串

Java21-统计字符串中每个字符出现的次数

算法第四章实践报告

全（十五）Jmeter 之 参数化 函数助手：__Random string（译：瑞德.丝锥）：随机字符串

生成随机字符串

标签