后缀自动机求母串不包含给定串子串的不同子串数量

首先，需要知道求两个串最长公共子串，即维护第二个串的每个前缀与第一个串的最长公共后缀。

对母串建一个 $sam$ ，所有串在 $sam$ 上面跑，并维护每个 $sam$ 上每个状态与所有的最长公共后缀长度，因此每个状态对答案的贡献为 $len(s) - dep(s)$ 。

可以理解原来状态的对子串数量的贡献为 $len(s) - len(link(s))$ ， $s$ 代表的子串长度区间中每个后缀都对答案有贡献，现在我们将这个区间拆成两块更新答案。

具体来讲，在获取所有点的 $dep$ 值后，基数排序获得 $sam$ 的状态的逆序拓扑排序。

因为需要对于每个状态更新他父亲节点的 $dep$ 值，所以遍历逆序拓扑排序。

这里需要同时从自动机和后缀树两个角度同时思考，当前节点的父亲也是当前节点的后缀，但是计算 $dep$ 时是自动机视角，所以当前节点和他的父亲计算的 $dep$ 没有影响，但实际上当前节点 $dep$ 值对他的父亲是有影响的，例如当前 $dep$ 超过了父亲节点的 $len$ ，父亲节点对答案是没有贡献的。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn = 100000 + 5;

ll ans[maxn << 1];

namespace sam{
    int len[maxn << 1], link[maxn << 1], ch[maxn << 1][26], tot, last;
    void init(){ ms(ans, -1); ms(ch, 0); tot = last = 1; }
    void insert(int c){
        int cur = ++tot, p = last;
        len[cur] = len[last] + 1; 
        for (; p && !ch[p][c]; p = link[p]) ch[p][c] = cur;
        if (!p) link[cur] = 1;
        else {
            int q = ch[p][c];
            if (len[p] + 1 == len[q]) link[cur] = q;
            else {
                int nq = ++tot; len[nq] = len[p] + 1;
                link[nq] = link[q]; link[q] = link[cur] = nq;
                memcpy(ch[nq], ch[q], sizeof ch[q]);
                for (; ch[p][c] == q; p = link[p]) ch[p][c] = nq;
            }
        } 
        last = cur;
    }
    
    int c[maxn << 1], a[maxn << 1];
    void rsort(){
        for (int i = 0; i <= tot; i++) c[i] = 0;
        for (int i = 1; i <= tot; i++) c[len[i]]++;
        for (int i = 1; i <= tot; i++) c[i] += c[i - 1];
        for (int i = 1; i <= tot; i++) a[c[len[i]]--] = i;
    }
}
using namespace sam;

char s[maxn];
int n, dep[maxn << 1];

int main(){
    int T, kase = 0; scanf("%d", &T);
    while (T--){
        scanf("%d%s", &n, s);
        init(); ms(dep, 0);
        for (int i = 0; s[i]; i++) insert(s[i] - 'a');
        while (n--){
            scanf("%s", s);
            int now = 1, l = 0;
            for (int i = 0; s[i]; i++){
                int c = s[i] - 'a';
                if (ch[now][c]) l++, now = ch[now][c], dep[now] = max(dep[now], l);
                else {
                    while (now && !ch[now][c]) now = link[now];
                    if (!now) now = 1, l = 0;
                    else l = len[now] + 1, now = ch[now][c], dep[now] = max(dep[now], l);
                }
            }
        }
        rsort(); ll ans = 0;
        for (int i = tot; i; i--){
            int now = a[i];
            if (dep[now]){
                dep[link[now]] = max(dep[link[now]], dep[now]);
                if (dep[now] < len[now]) ans += len[now] - dep[now];
            }
            else ans += len[now] - len[link[now]];
        }
        printf("Case %d: %lld\n", ++kase, ans);
    }
    return 0;
}

跃迁引擎启动

HDu4416 Good Article Good sentence

代码