http://www.lydsy.com/JudgeOnline/problem.php?id=2434

Brief description:

… 要求你维护一组字符串、和一个文本框。。支持下列操作：

• 输入一个小写字母。
• 退格。
• 保存当前文本框中的字符串。
• 询问第 x 个保存的字符串，在第 y 个保存的字符串中，出现多少次。

Analysis:

树状数组维护 fail 树。

。。。。考虑已经构建好 ACM，那么每次询问可以在 ACM 上拼写 y。。。

http://vjudge.net/problem/viewProblem.action?id=16405

inline int Run(){
        int ans = 0; RS(str), u = 0; REP_S(cur, str){
            for (int t = u = v; t; t = faill[t]) if (id[t] == x) ++ans;
        }
        return ans;     
} 

考察 Fail 树，从文本串前缀所在的某个状态 t 出发沿着 fail 指针到根结点的路径上包含 p（模式串所代表的状态）。。
当且仅当 t 处在 p 为根的子树中。。。

。。因此我们考虑离线用树状数组维护 fail 树的 dfs 序列。。。

https://gist.github.com/lychees/6788733

首先构建出 ACM && fail 树 && dfs 序列。。 之后处理文本串 t，每增加一个字符，就标记一下当前所在的节点。
每次询问 p 时候。。看模式串 p 所对应的子树被标记的次数即可。。

   Init(); int ti = 0; u = 0; REP(i, cn) switch (cmd[i]){
        case 'P':
            ECH(it, qry[ti]) ans[it->fi] = Sum(L[pos[it->se]], R[pos[it->se]]);
            ++ti;
            break;
        case 'B':
            Add(L[u], -1);
            u = p;
            break;
        default:
            Add(L[u = v], 1);
    }

Posted by xiaodao
Category: 日常