反思

· · 个人记录

P4045 [JSOI2009] 密码

这道题考察 AC自动机。

关于多个字符串匹配可以考虑到 AC自动机 上跑 DP。

有几点注意：

  1. 注意 Fail 树的祖先是已经跑过的子串。

  2. 在记忆化的时候：区分 -1、0、1。尽量使用 == 号区分，不容易出错。

  3. dfs 输出方案时要先保存在数组中，很多时候不能边输出边递归。

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

思想：和 马拉车差不多，把前面已经算过的直接套用。

功能：求一个字符串 S 的所有后缀 S[i,|S|] 与文本 S 的 LCP（最长公共前缀）。

有一些要关注点：

  1. 字符串下标从 1 开始时要注意细节，尤其重构代码时。

  2. 算时用了 long long 结果返回值用了 int。建议使用 auto 作为返回值。

#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;
}