BZOJ 2434. [Noi2011]阿狸的打字機

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);
    }