Brief description:

给定一段 Text、以及 nn 个 Pattern。要求这个 Text 中合法的子串数目，使得对于第 ii 个 Pattern，恰好能够匹配 [l_ii, r_ii] 之间次。
（nn ≤ 10）

Analysis:

SAM-DP。

我们把涉及到的所有字符串（Text && Patterns），依次插入到 SAM。（相邻的字符串之间，用彼此不同的分隔符隔开，以保证各字符串之间在 SAM 中不会相互干扰）
dp[ii][u] 表示：结点 u 所表示的子串集合，对于第 ii 个字符串的匹配次数。

http://codeforces.com/contest/316/submission/4749994

namespace SAM{

    const int SN = int(5e4) + 1, NN = 11, N = 2*NN*SN + 9, Z = 26;

    int trans[N][Z+NN], fail[N], len[N], tail, tot; char str[SN];

    inline int new_node(){
        // RST(trans[tot);
        tail = tot;
        return tot++;
    }
    inline int new_node(int u){
        CPY(trans[tot], trans[u]), fail[tot] = fail[u];
        return tot++;
    }

#define v trans[u][c]
#define f fail[u]
#define ff fail[uu]

    inline int h(int u){
        return len[u] - len[f];
    }

    void Ext(int c){
        int u = tail, uu = new_node(); len[uu] = len[u] + 1;
        while (u && !v) v = uu, u = f;
        if (!u && !v) v = uu, ff = 0;
        else{
            if (len[v] == len[u] + 1) ff = v;
            else{
                int _v = v, vv = new_node(_v); len[vv] = len[u] + 1;
                fail[_v] = ff = vv;
                while (v == _v) v = vv, u = f;
            }
        }
    }

    int dp[NN][N], l[NN], r[NN]; bool vis[N];
    int nn, ans;
#define c (*cur - 'a')
    void Init(){
        tot = 0, new_node();
        gets(str); REP_S(cur, str) Ext(c); Ext(Z);
        REP_1_C(ii, RD(nn)){
            RS(str); RD(l[ii], r[ii]);
            REP_S(cur, str) Ext(c); Ext(Z+ii);
        }
    }
#undef c

    inline bool legal(int u){
        if (!u || !dp[0][u]) return 0;
        REP_1(ii, nn) if (dp[ii][u] < l[ii] || r[ii] < dp[ii][u]) return 0;
        return 1;
    }

    void dfs(int u = 0){
        if (vis[u]) return; vis[u] = 1;

        REP(ii, nn+1) if (trans[u][Z+ii]) dp[ii][u] = 1;

        REP(c, Z) if (v){
            dfs(v); REP(ii, nn+1) dp[ii][u] += dp[ii][v];
        }

        if (legal(u)) ans += h(u);
    }

} using namespace SAM;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    Init(); dfs(); OT(ans);
}

Posted by xiaodao
Category: Codeforces
Tags: 后缀三姐妹