Border树

对于一个字符串S，n = |S|，它的Border 树（也叫next 树）共有n+1
个节点：0, 1, 2, . . . , n。
0 是这棵有向树的根。对于其他每个点1 ≤ i ≤ n，父节点为next[i]。

struct KMP {
    vector<int> nxt;
    string tt;
    int len;
    KMP() {}
    KMP(string t) {
        len = t.size();
        t = " " + t;
        tt = t;
        nxt.resize(len + 1);
        nxt[1] = nxt[0] = 0;
        init(tt);
    }

    void init(string t) {
        for (int i = 2; i <= len; i++) {
            nxt[i] = nxt[i - 1];
            while (nxt[i] && t[i] != t[nxt[i] + 1]) nxt[i] = nxt[nxt[i]];
            nxt[i] += (t[i] == t[nxt[i] + 1]);
        }
    }
    void buildtree(auto& e) {
        for (int i = 1; i <= len; i++) {
            e[nxt[i]].emplace_back(i);
        }
    }
};

性质:next[i] 表示字符串 S 的前缀 Prefix[i] 的非平凡的最大 Border。

  1. 每个前缀Prefix[i] 的所有Border：节点i 到根的链。
  2. 哪些前缀有长度为x 的Border：x 的子树。前缀x出现了子树大小siz[x]次
  3. 求两个前缀的最长公共Border 等价于求LCA。

1.给定一个字符串 $s$，定义它的 $k$ 前缀 $\mathit{pre}k$ 为字符串 $s{1\dots k}$，$k$ 后缀 $\mathit{suf}k$ 为字符串 $s{|s|-k+1\dots |s|}$，其中 $1 \le k \le |s|$。

定义 $\bold{Border}(s)$ 为对于 $i \in [1, |s|)$，满足 $\mathit{pre}_i = \mathit{suf}_i$ 的字符串 $\mathit{pre}_i$ 的集合。$\bold{Border}(s)$ 中的每个元素都称之为字符串 $s$ 的 $\operatorname{border}$。

有 $m$ 组询问，每组询问给定 $p,q$，求 $s$ 的 $\boldsymbol{p}$ 前缀 和 $\boldsymbol{q}$ 前缀 的 最长公共 $\operatorname{border}$ 的长度。

Sol:建立border树，等价于求两者的lca。由于求的是非平凡，如果存在一个前缀是另一个前缀的border，则需要跳到父亲

debug：树剖的板子要加双向边并且注意坐标偏移从1-n+1

void solve() {
    string s;cin >> s; KMP kmp(s);
    int n = s.size();HLD hld(n + 1);// 字符串长度加上一个空节点
    for (int i = 1; i <= kmp.len; i++) {  // 一定要加双向边
        hld.addEdge(kmp.nxt[i] + 1, i + 1);
        hld.addEdge(i + 1, kmp.nxt[i] + 1);
    }
    hld.work(1);
    int m;cin >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        x++;//进行下标偏移。考虑到dfs序问题(0-n)->(1-n+1)
        y++;
        int res = hld.lca(x, y);
        if (x == res || y == res)//如果一个前缀是另一个前缀border，找父亲
            cout << hld.parent[res] - 1 << endl;
        else
            cout << res - 1 << endl;
    }
}

//倍增版本
void solve() {
    string s;
    cin >> s;
    KMP kmp(s);
    int n = s.size();
    Blca lc(n + 1);                       // 字符串长度加上一个空节点
    for (int i = 1; i <= kmp.len; i++) {  // 一定要加双向边
        lc.add(kmp.nxt[i] + 1, i + 1);
    }
    lc.dfs(1, 0);
    int m;
    cin >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        x++;  // 进行下标偏移。考虑到dfs序问题(0-n)->(1-n+1)
        y++;
        int res = lc.lca(x, y);
        if (x == res || y == res)  // 如果一个前缀是另一个前缀border，找父亲
            cout << lc.st[res][0] - 1 << endl;
        else
            cout << res - 1 << endl;
    }
}

2.字符串S 长度不超过106，求一个最长的子串T，满足：

  • T 为S 的前缀。

  • T 为S 的后缀。

  • T 在S 中至少出现K次。

Sol:考虑T是border，出现k次等价于子树比k大，我们只需要把树建出来，然后dfs一遍求子树大小就可以了

void solve() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    KMP kmp(s);
    vector<vector<int>> e(n + 1);
    kmp.buildtree(e);
    vector<int> sz(n + 1);
    auto dfs = [&](auto self, int u)->void {
        sz[u] = 1;
        for (auto v : e[u]) {
            self(self, v);
            sz[u] += sz[v];
        }
    };
    dfs(dfs,0);
    int ans = 0;
    for (int i = n; i; i = kmp.nxt[i]) {
        if (sz[i] >= k)
            ans = max(ans, i);
    }
   if(ans==0)cout<<-1;else cout<<s.substr(0,ans);
}

3.字符串S 长度不超过200, 000，有Q ≤ 200, 000 次操作：

  1. 修改操作：向字符串末尾添加一个字符ch。

  2. 查询操作：求一个最长的子串T，满足：
    T 为S 的前缀。
    T 为S 的后缀。
    T 在S 中至少出现K次。

Sol：考虑离线询问，先把完整的fail树建立。然后每次询问的子树大小，我们动态维护标记，从当前结尾开始倍增每次用树状数组查询带标记子树大小。倍增需要特判一开始就满足条件的情况。

debug：两层for变量用重，导致RE。倍增需要特判一开始就满足条件的情况。由于树状数组下标不能为0，而fail树中存在0号节点，但dfs序我们又规定了从1开始标号，每次都是在dfs序的意义下修改树状数组，所以不需要偏移了。牢记Fwk初始化都传入节点数就可以了

void solve() {
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    int cnt = n;
    vector<node> q(m + 1);
    for (int i = 1; i <= m; i++) {
        cin >> q[i].op;
        if (q[i].op == 1) {
            cin >> q[i].c;
            s += q[i].c;
            cnt += 1;
            q[i].x = cnt;
        } else {
            cin >> q[i].x;
        }
    }
    deb(s);
    KMP kmp(s);
    Blca lc(cnt + 1);
    kmp.buildtree(lc.e);
    lc.dfs(0, 0);
    Fwk<int> fw(cnt + 1);  // 树状数组下标偏移
    for (int i = 1; i <= n; i++) fw.add(l[i], 1);
    // 主要是建树
    int p = n;
    for (int i = 1; i <= m; i++) {
        if (q[i].op == 1) {
            p = q[i].x;
            fw.add(l[p], 1);
        } else {
            int cur = p;
            if (fw.rangeSum(l[cur] - 1, r[cur]) >= q[i].x) {
                cout << cur << endl;
                continue;
            }
            for (int j = lc.len; j >= 0; j--) {
                int pos = lc.st[cur][j];
                deb(pos, fw.rangeSum(l[pos] - 1, r[pos]));
                if (fw.rangeSum(l[pos] - 1, r[pos]) < q[i].x)
                    cur = pos;
            }
            deb(cur);
            if (lc.st[cur][0])
                cout << lc.st[cur][0] << endl;
            else
                cout << -1 << endl;
        }
        deb(i, p);
    }
}

可持久化KMP，nxt图（类比triw图

https://codeforces.com/contest/1721/problem/E

https://www.cnblogs.com/Blue233333/p/8241503.html

https://blog.csdn.net/ghu99999/article/details/118707728

https://www.luogu.com.cn/problem/CF808G