专栏文章

反思

qqinsishi
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqb4sq5
此快照首次捕获于
2025/12/04 01:55
3 个月前
此快照最后确认于
2025/12/04 01:55
3 个月前
查看原文

P4045 [JSOI2009] 密码

这道题考察 AC自动机。
关于多个字符串匹配可以考虑到 AC自动机 上跑 DP。
有几点注意：
  1. 注意 Fail 树的祖先是已经跑过的子串。
  2. 在记忆化的时候：区分 -1、0、1。尽量使用 == 号区分，不容易出错。
  3. dfs 输出方案时要先保存在数组中，很多时候不能边输出边递归。

P5410 【模板】扩展 KMP/exKMP（Z 函数）

思想：和 马拉车差不多，把前面已经算过的直接套用。
功能：求一个字符串 SS 的所有后缀 S[i,∣S∣]S[i,|S|] 与文本 SS 的 LCP（最长公共前缀）。
有一些要关注点：
  1. 字符串下标从 1 开始时要注意细节，尤其重构代码时。
  2. 算时用了 long long 结果返回值用了 int。建议使用 auto 作为返回值。
CPP
#include <bits/stdc++.h>
using namespace std;



void exkmp(string s) {
	vector<int> z;
	int n = s.size();
	z.resize(n); z[0] = n; 
	int x = 0, p = 0;
	for (int i=1; i<n; ++i) {
		z[i] = 0;
		int l = z[i-x]; 
		if (i <= p) z[i] = min(l, p-i+1);
		while (i+z[i] < n && s[z[i]] == s[i+z[i]]) ++z[i];
		if (i+z[i]-1 > p) x = i, p = i+z[i]-1;
	}
}

auto cal() {
	long long ret = 0;
	for (int i=0; i<z.size(); ++i) {
		ret ^= (long long)(i+1)*(z[i]+1);
	}
	return ret;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	string a, b;
	cin >> a >> b;
	exkmp(b); 
	cout << cal() << '\n';
	exkmp(b+"#"+a);
	z.erase(z.begin(), z.begin()+b.size()+1);
	cout << cal() << '\n';
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...