洛谷P4070 生成魔咒-白红宇

洛谷P4070 生成魔咒

阅读量：7119 次

发布时间：2019-06-28

本文共 1705 字，大约阅读时间需要 5 分钟。

题意：给定字符串，求每个前缀的本质不同的子串数量。字符集1e9。

解：在线构造后缀自动机并统计答案。

答案就是∑len[i] - len[fail[i]]

每次增加的时候，至多对三个节点有影响。然而把Q分裂为nQ本质不同的子串数没变。

于是增加的只有len[np] - len[fail[np]]

map维护转移边。

1 #include 
      
        2 #include 
        3  4 typedef long long LL; 5 const int N = 200010; 6  7 int len[N], fail[N], last, top; 8 LL ans; 9 std::map
        
          mp[N];10 11 inline void init() {12     top = last = 1;13     return;14 }15 16 inline void insert(int f) {17     int p = last, np = ++top;18     last = np;19     len[np] = len[p] + 1;20     while(p && !mp[p].count(f)) {21         mp[p][f] = np;22         p = fail[p];23     }24     //printf("p = %d \n", p);25     if(!p) {26         fail[np] = 1;27         ans += len[np];28         //printf("1 : ans += %d \n", len[np]);29     }30     else {31         int Q = mp[p][f];32         //printf("Q = %d \n", Q);33         if(len[Q] == len[p] + 1) {34             fail[np] = Q;35             ans += len[np] - len[Q];36             //printf("2 : ans += %d \n", len[np] - len[Q]);37         }38         else {39             int nQ = ++top;40             len[nQ] = len[p] + 1;41             fail[nQ] = fail[Q];42             fail[Q] = fail[np] = nQ;43             mp[nQ] = mp[Q];44             while(mp[p].count(f) && mp[p][f] == Q) {45                 mp[p][f] = nQ;46                 p = fail[p];47             }48             ans += len[np] - len[nQ];49         }50     }51     return;52 }53 54 int main() {55     int n;56     scanf("%d", &n);57     init();58     for(int i = 1, x; i <= n; i++) {59         scanf("%d", &x);60         insert(x);61         printf("%lld\n", ans);62     }63 64     return 0;65 }

AC代码

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

你可能感兴趣的文章

发布/订阅模式

查看>>

eyoucms uihtml 带html富文本可视化标签