洛谷P2414 阿狸的打字机

清疚 2022-01-09 04:03 221阅读 0赞

题意：以trie的形式给出n个字符串，每次询问第x个字符串在第y个字符串中出现了几次。

解：总串长是n2级别的，所以不能用什么后缀自动机...

\[update\]可以建triesam但是不知道trie上的一个节点对应到了sam上的哪几个节点...感觉可以做...好混乱

听说是个AC自动机上DP，然后怎么想状态都是n²的，然后看题解发现跟DP没啥关系...

是这样的：对于x在y中出现的每一次，我们把它的前面一直补齐，这样每个串就对应着y的一个前缀，且这个前缀的一个后缀是x。

可知，trie上y节点到根的链就代表这些前缀。

然后要求后缀是x。因为x也在这些串中出现了，所以这些前缀一直跳fail的话一定会跳到x节点。即他们全都在x的fail树的子树中。

然后我们就发现，trie上y到根的路径上的节点和fail树上x的子树的节点的交就是答案。

一个很朴素的想法就是把这两棵树剖出来，就是一个二维数点问题。把主席树建出来，因为用了树剖所以每次回答询问是nlog²n的，可以做到在线。

一个高端想法就是离线下来，按照fail树建DFS序。在trie上DFS，维护trie树上当前节点到根的路径权值为1，别的地方为0。

然后查询就是当在trie上DFS到y的时候，查询x在fail树中的子树权值和。

这是单点修改，区间查询。树状数组即可。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <cstdio>
      2 #include <cstring>
      3 #include <algorithm>
      4 #include <stack>
      5 #include <queue>
      6 #include <vector>
      7 
      8 const int N = 100010;
      9 
     10 struct Edge {
     11     int nex, v;
     12 }edge[N << 1]; int top;
     13 
     14 struct Node {
     15     int x, y, ans;
     16 }node[N];
     17 
     18 int tr[N][26], fail[N], tot = 1;
     19 char str[N];
     20 int ed[N], e[N], pos[N], siz[N], num;
     21 std::vector<int> v[N];
     22 
     23 namespace bit {
     24     int ta[N];
     25     inline void add(int p) {
     26         for(int i = p; i < N; i += i & (-i)) {
     27             ta[i]++;
     28         }
     29         return;
     30     }
     31     inline void del(int p) {
     32         for(int i = p; i < N; i += i & (-i)) {
     33             ta[i]--;
     34         }
     35         return;
     36     }
     37     inline int getSum(int p) {
     38         int ans = 0;
     39         for(int i = p; i >= 1; i -= i & (-i)) {
     40             ans += ta[i];
     41         }
     42         return ans;
     43     }
     44     inline int ask(int l, int r) {
     45         return getSum(r) - getSum(l - 1);
     46     }
     47 }
     48 
     49 inline void add(int x, int y) {
     50     top++;
     51     edge[top].v = y;
     52     edge[top].nex = e[x];
     53     e[x] = top;
     54     return;
     55 }
     56 
     57 inline void getAC() {
     58     std::stack<int> S;
     59     std::queue<int> Q;
     60     int n = strlen(str), t = 0, p = 1;
     61     for(int i = 0; i < n; i++) {
     62         if(str[i] == 'P') {
     63             ed[++t] = p;
     64             continue;
     65         }
     66         if(str[i] == 'B') {
     67             if(!S.empty()) {
     68                 p = S.top();
     69                 S.pop();
     70             }
     71             continue;
     72         }
     73         int f = str[i] - 'a';
     74         if(!tr[p][f]) {
     75             tr[p][f] = ++tot;
     76         }
     77         S.push(p);
     78         p = tr[p][f];
     79     }
     80     // getfail
     81     fail[1] = 1;
     82     Q.push(1);
     83     while(!Q.empty()) {
     84         int x = Q.front();
     85         Q.pop();
     86         for(int f = 0; f < 26; f++) {
     87             if(!tr[x][f]) {
     88                 continue;
     89             }
     90             int y = tr[x][f], j = fail[x];
     91             while(!tr[j][f] && j != 1) {
     92                 j = fail[j];
     93             }
     94             if(tr[j][f] && x != 1) {
     95                 j = tr[j][f];
     96             }
     97             fail[y] = j;
     98             add(j, y);
     99             Q.push(y);
    100         }
    101     }
    102     return;
    103 }
    104 
    105 void DFS_1(int x) {
    106     pos[x] = ++num;
    107     siz[x] = 1;
    108     for(int i = e[x]; i; i = edge[i].nex) {
    109         int y = edge[i].v;
    110         DFS_1(y);
    111         siz[x] += siz[y];
    112     }
    113     return;
    114 }
    115 
    116 void DFS_2(int x) {
    117     bit::add(pos[x]);
    118     for(int i = 0; i < v[x].size(); i++) {
    119         int t = node[v[x][i]].x;
    120         node[v[x][i]].ans = bit::ask(pos[ed[t]], pos[ed[t]] + siz[ed[t]] - 1);
    121     }
    122     for(int i = 0; i < 26; i++) {
    123         if(tr[x][i]) {
    124             DFS_2(tr[x][i]);
    125         }
    126     }
    127     bit::del(pos[x]);
    128     return;
    129 }
    130 
    131 int main() {
    132     scanf("%s", str);
    133     //
    134     getAC();
    135     DFS_1(1);
    136     int m;
    137     scanf("%d", &m);
    138     for(int i = 1; i <= m; i++) {
    139         scanf("%d%d", &node[i].x, &node[i].y);
    140         v[ed[node[i].y]].push_back(i);
    141     }
    142 
    143     DFS_2(1);
    144 
    145     for(int i = 1; i <= m; i++) {
    146         printf("%d \n", node[i].ans);
    147     }
    148     return 0;
    149 }

AC代码

转载于:https://www.cnblogs.com/huyufeifei/p/10327614.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220109/21b982f22cd84ab88fc0f18d492d39aa.png