NOI2018 你的名字——SAM+线段树合并

题目链接在这里洛谷/LOJ

题目大意

有一个串\(S\)，每次询问给你一个串\(T\)，两个数\(L\)和\(R\)，问你\(T\)有多少个本质不同的子串不是\(S[L,R]\)的子串

SOLUTION

如果你做过生成魔咒和CF1037H，就会做这道题了
有两个坑点：
1.线段树合并时必须每次都新建结点，因为两颗树都得保留
2.每次失配时必须先尝试减小已经匹配的长度，无法继续减少时再跳\(suflink\)
我的大常数代码

#include <algorithm>
#include  <iostream>
#include   <cstdlib>
#include   <cstring>
#include    <cstdio>
#include    <random>
#include    <string>
#include    <vector>
#include     <cmath>
#include     <ctime>
#include     <queue>
#include       <map>
#include       <set>

#define IINF 0x3f3f3f3f3f3f3f3fLL
#define u64 unsigned long long
#define pii pair<int, int>
#define mii map<int, int>
#define u32 unsigned int
#define lbd lower_bound
#define ubd upper_bound
#define INF 0x3f3f3f3f
#define vi vector<int>
#define ll long long
#define mp make_pair
#define pb push_back
#define is insert
#define se second
#define fi first
#define ps push

#define $SHOW(x) cout << #x" = " << x << endl
#define $DEBUG() printf("%d %s\n", __LINE__, __FUNCTION__)

using namespace std;

#define S 500000
#define Q 100000
#define T 1000000
#define mid ((l+r)>>1)

int q, n, m, L, R;
char s[S+5], t[T+5];
int nid1 = 1, lst1 = 1, ch1[26][2*S+5], link1[2*S+5], len1[2*S+5], nodecnt, root[2*S+5], ch[2][200*S+5];
int nid, lst, nxt[26][2*T+5], link[2*T+5], len[2*T+5], rest[2*T+5], val[T+5];
ll ans = 0;
int a[2*T+5], buc[2*T+5];

void add(int &o, int l, int r, int x) {
    if (!o) o = ++nodecnt;
    if (l == r) return ;
    if (x <= mid) add(ch[0][o], l, mid, x);
    else add(ch[1][o], mid+1, r, x);
}

int merge(int x, int y, int l, int r) {
    int u = ++nodecnt;
    if (x * y == 0) u = x ? x : y;
    else {
        ch[0][u] = merge(ch[0][x], ch[0][y], l, mid);
        ch[1][u] = merge(ch[1][x], ch[1][y], mid + 1, r);
    }
    return u;
}

int query(int u, int l, int r, int L, int R) {
    if (!u) return 0;
    if (L <= l && r <= R) return 1;
    int ret = 0;
    if (L <= mid) ret |= query(ch[0][u], l, mid, L, R);
    if (R > mid) ret |= query(ch[1][u], mid+1, r, L, R);
    return ret;
}

void build() {
    for (int i = 1, c; i <= n; ++i) {
        c = s[i] - 'a';
        int cur = ++nid1;
        len1[cur] = len1[lst1] + 1;
        add(root[cur], 1, n, i);
        while (lst1 && !ch1[c][lst1]) ch1[c][lst1] = cur, lst1 = link1[lst1];
        if (!lst1) link1[cur] = 1;
        else {
            int p = lst1, q = ch1[c][lst1];
            if (len1[q] == len1[p] + 1) link1[cur] = q;
            else {
                int clone = ++nid1;
                len1[clone] = len1[p] + 1;
                for (int j = 0; j < 26; ++j) ch1[j][clone] = ch1[j][q];
                link1[clone] = link1[q], link1[cur] = link1[q] = clone;
                while (p && ch1[c][p] == q) ch1[c][p] = clone, p = link1[p];
            }
        }
        lst1 = cur;
    }
    for (int i = 1; i <= nid1; ++i) buc[len1[i]]++;
    for (int i = 1; i <= n; ++i) buc[i] += buc[i-1];
    for (int i = 1; i <= nid1; ++i) a[buc[len1[i]]--] = i;
    for (int i = nid1; i >= 2; --i) root[link1[a[i]]] = merge(root[link1[a[i]]], root[a[i]], 1, n);
}

void extend(int c) {
    int cur = ++nid;
    len[cur] = len[lst] + 1;
    for(int i = 0; i < 26; ++i) nxt[i][cur] = 0;
    while (lst && !nxt[c][lst]) nxt[c][lst] = cur, lst = link[lst];
    if (!lst) link[cur] = 1;
    else {
        int p = lst, q = nxt[c][lst];
        if (len[q] == len[p] + 1) link[cur] = q;
        else {
            int clone = ++nid;
            len[clone] = len[p] + 1;
            for (int i = 0; i < 26; ++i) nxt[i][clone] = nxt[i][q];
            link[clone] = link[q], link[q] = link[cur] = clone;
            while (p && nxt[c][p] == q) nxt[c][p] = clone, p = link[p];
        }
    }
    lst = cur;
}

void calc() {
    m = strlen(t+1);
    lst = nid = 1;
    int i, j, c;
    for (i = 0; i < 26; ++i) nxt[i][1] = 0;
    for (j = 1; j <= m; ++j) extend(t[j] - 'a');
    for (i = 2; i <= nid; ++i) rest[i] = 0;
    int u = 1, match = 0;
    for (i = 1, c; i <= m; ++i) {
        c = t[i] - 'a';
        while (u && !query(root[ch1[c][u]], 1, n, L + match, R)) {
            if(match > len1[link1[u]]) match--;
            else u = link1[u], match = len1[u];
        }
        if (!u) u = 1, match = 0;
        else u = ch1[c][u], match++;
        val[i] = match;
    }
    u = 1;
    for (i = 1; i <= m; ++i) u = nxt[t[i] - 'a'][u], rest[u] = val[i];
    for (i = 0; i <= m; ++i) buc[i] = 0;
    for (i = 1; i <= nid; ++i) buc[len[i]]++;
    for (i = 1; i <= m; ++i) buc[i] += buc[i-1];
    for (i = 1; i <= nid; ++i) a[buc[len[i]]--] = i;
    for (i = nid; i >= 2; --i) rest[link[a[i]]] = max(rest[link[a[i]]], rest[a[i]]);
    ll ans = 0;
    for (i = 2; i <= nid; ++i) ans += max(0, min(len[i] - rest[i], len[i] - len[link[i]]));
    printf("%lld\n", ans);
}

int main() {
    scanf("%s", s+1);
    n = strlen(s+1);
    build();
    scanf("%d", &q);
    for (int i = 1; i <= q; ++i) {
        scanf("%s%d%d", t+1, &L, &R);
        calc();
    }
    return 0;
}

NOI2018 你的名字——SAM+线段树合并

原文：https://www.cnblogs.com/dummyummy/p/11037727.html