你的名字 题解

你的名字

首先考虑一下，\tt l = 1, r = |S| 的情况。

既然是字符串匹配，所以是考虑对于每一个字符串都建立一个 SAM。

然后考虑会有字符重复。

我们想象之前求本质不同的字符串的个数是什么。

ans = \sum maxlen[i] - maxlen[fa[i]]

但是对于一个 endpos 的集合里面，会存在有些后缀正好和不合法的串相同。

我们考虑进行预处理匹配，之后答案就是 \sum \max(0, maxlen[i] - \max(maxlen[fa[i]], lim[i]))

但是我们注意一下，后面的 lim[i] 应该是对于该集合的 endpos 的集合进行匹配。

那么我们需要记录的是第一个出现这个长度的点（结尾位置），也就是位置，我们用 tag[i] 记录。

之后考虑 l, r 任意的情况。

需要考虑的是这些位置有没有出现过。

可以考虑在之前做的情况上进行改进。

我们可以参考 \tt CF666E

用线段树合并来维护当前位置是否被使用过。（区间）

这里考虑哪个是固定的

显然是这个 |S|

那么我们考虑让每一个 |T| 去按位匹配 |S|

假设已经匹配了 len 位，区间是 [l, r]

我们需要知道在 [l + len, r] 这个区间中 |S| 是否有节点存在

这个区间指的是长度，因为我们匹配的是后缀。

对于一个匹配失败的情况，我们考虑倒退一位。

#include <bits/stdc++.h>
/*
* @ legendgod
* 是啊……你就是那只鬼了……#include <bits/stdc++.h>
*/
using namespace std;

//#define Fread
// #define Getmod

#ifdef Fread
char buf[1 << 21], *iS, *iT;
#define gc() (iS == iT ? (iT = (iS = buf) + fread (buf, 1, 1 << 21, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
#endif // Fread

template <typename T>
void r1(T &x) {
    x = 0;
    char c(getchar());
    int f(1);
    for(; c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;
    for(; '0' <= c && c <= '9';c = getchar()) x = (x * 10) + (c ^ 48);
    x *= f;
}

#ifdef Getmod
const int mod  = 1e9 + 7;
template <int mod>
struct typemod {
    int z;
    typemod(int a = 0) : z(a) {}
    inline int inc(int a,int b) const {return a += b - mod, a + ((a >> 31) & mod);}
    inline int dec(int a,int b) const {return a -= b, a + ((a >> 31) & mod);}
    inline int mul(int a,int b) const {return 1ll * a * b % mod;}
    typemod<mod> operator + (const typemod<mod> &x) const {return typemod(inc(z, x.z));}
    typemod<mod> operator - (const typemod<mod> &x) const {return typemod(dec(z, x.z));}
    typemod<mod> operator * (const typemod<mod> &x) const {return typemod(mul(z, x.z));}
    typemod<mod>& operator += (const typemod<mod> &x) {*this = *this + x; return *this;}
    typemod<mod>& operator -= (const typemod<mod> &x) {*this = *this - x; return *this;}
    typemod<mod>& operator *= (const typemod<mod> &x) {*this = *this * x; return *this;}
    int operator == (const typemod<mod> &x) const {return x.z == z;}
    int operator != (const typemod<mod> &x) const {return x.z != z;}
};
typedef typemod<mod> Tm;
#endif

template <typename T,typename... Args> inline void r1(T& t, Args&... args) {
    r1(t);  r1(args...);
}

//#define int long long
const int maxn = 1e6 + 5;
const int maxm = 2e7 + 5;
int n, m;
struct Node {
    int c[26], len, fa;
    Node(void) {
        memset(c, 0, sizeof(c)), len = fa = 0;
    }
};
char S[maxn];
int rt[maxn], len[maxn];

namespace T {
    int tot(0);
    int L[maxm], R[maxm];
    #define ls L[p]
    #define rs R[p]
    #define mid ((l + r) >> 1)
    void Insert(int &p,int l,int r,int pos) {
        if(!p) p = ++ tot;
        if(l == r) return ;
        if(pos <= mid) Insert(ls, l, mid, pos);
        else Insert(rs, mid + 1, r, pos);
    }
    int merge(int u,int v) {
        if(!u || !v) return u + v;
        int now = ++ tot;
        L[now] = merge(L[u], L[v]);
        R[now] = merge(R[u], R[v]);
        return now;
    }
    bool Ask(int p,int l,int r,int ll,int rr) {
        if(!p) return false;
        if(ll <= l && r <= rr) return true;
        bool res(false);
        if(ll <= mid) res |= Ask(ls, l, mid, ll, rr);
        if(mid < rr) res |= Ask(rs, mid + 1, r, ll, rr);
        return res;
    }
};

namespace SAM {
    Node d[maxn << 1];
    int c[maxn << 1], t[maxn << 1], in[maxn << 1];
    int tot(1), las(1);
    void Insert(int c) {
        int p = las, np = las = ++ tot;
        in[np] = 1;
        d[np].len = d[p].len + 1;
        for(; p && !d[p].c[c]; p = d[p].fa) d[p].c[c] = np;
        if(!p) d[np].fa = 1;
        else {
            int q = d[p].c[c];
            if(d[q].len == d[p].len + 1) d[np].fa = q;
            else {
                int nq = ++ tot; d[nq] = d[q];
                d[nq].len = d[p].len + 1;
                d[q].fa = d[np].fa = nq;
                for(; p && d[p].c[c] == q; p = d[p].fa) d[p].c[c] = nq;
            }
        }
    }
    void Solve() {
        memset(c, 0, sizeof(c)), memset(t, 0, sizeof(t));
        int i;
        for(i = 1; i <= n; ++ i) Insert(S[i] - 'a');
        for(i = 1; i <= tot; ++ i) ++ c[d[i].len];
        for(i = 1; i <= tot; ++ i) c[i] += c[i - 1];
        for(i = 1; i <= tot; ++ i) t[c[d[i].len] --] = i;
        for(i = tot; i; -- i) {
            int u = t[i];
            if(in[u]) T::Insert(rt[u], 1, n, d[u].len);
            rt[d[u].fa] = T::merge(rt[d[u].fa], rt[u]);
        }
    }
}

namespace Calc {
    int tot(1), las(1);
    Node d[maxn << 1];
    int tag[maxn << 1];
    void init() {
        for(int i = 1; i <= tot; ++ i) d[i] = Node();
        tot = las = 1;
    }

    void Insert(int c) {
        int p = las, np = las = ++ tot;
        d[np].len = tag[np] = d[p].len + 1;
        for(; p && !d[p].c[c]; p = d[p].fa) d[p].c[c] = np;
        if(!p) d[np].fa = 1;
        else {
            int q = d[p].c[c];
            if(d[q].len == d[p].len + 1) d[np].fa = q;
            else {
                int nq = ++ tot; d[nq] = d[q];
                tag[nq] = tag[q];
                d[nq].len = d[p].len + 1;
                d[np].fa = d[q].fa = nq;
                for(; p && d[p].c[c] == q; p = d[p].fa) d[p].c[c] = nq;
            }
        }
    }

    void main() {
        init();
        int i, j, L, R;
        scanf("%s", S + 1);
        r1(L, R);
        m = strlen(S + 1);
        int p(1), ln(0);
        for(i = 1; i <= m; ++ i) {
            int c = S[i] - 'a';
            Insert(c);
            while(1) {
                if(SAM::d[p].c[c] && T::Ask(rt[SAM::d[p].c[c]], 1, n, L + ln, R)) {
                    ++ ln, p = SAM::d[p].c[c]; break;
                }
                if(ln == 0) break;
                -- ln; // reduce the first char and find another answer
                if(SAM::d[SAM::d[p].fa].len == ln) p = SAM::d[p].fa;
                // we should find the endpos which is satisfied the position of appearances
                // or we can't find a right endpos so we ought to wait the other char
            }
            len[i] = ln;
        }
        long long ans(0);
        for(i = 2; i <= tot; ++ i)
            ans += max(0, d[i].len - max(d[d[i].fa].len, len[tag[i]]));
        printf("%lld\n", ans);
//        puts("St");
//        for(i = 1; i <= tot; ++ i) printf("%d ", tag[i]);
//        puts("End");
        return ;
    }
}

/*
scbamgepe
3
smape 2 7
sbape 3 8
sgepe 1 9

scbamgepe
2
sbape 3 8
sgepe 1 9
*/

signed main() {
//    freopen(".in", "r", stdin);
//    freopen(".out", "w", stdout);
    int i, j;
    scanf("%s", S + 1);
    n = strlen(S + 1);
    SAM::Solve();
    int q; r1(q);
    while(q --) Calc::main();
    return 0;
}