[KMP][倍增求LCA]JZOJ 4669 弄提纲

Bertha 。 2021-12-16 01:07 326阅读 0赞

#### Description ####

新日暮里中，比冲是一位博学的哲学教授。由于最近要帮学生准备考试，他决定弄个提纲给学生。然而同事van不服气，觉得这样学生就没有了自我思考，便在提纲中添加废话。  
比冲很无奈，他想找回原稿。我们把现在的提纲看成是一个字符串S。他知道van只会在原稿结尾添加语句，也就是说，原稿是S的前缀。  
现在比冲有m个询问，以此来找出原稿。每次给出两个位置l,r，问以l与r结尾的字符串中，有多少个字符串符合原稿的性质，最长的有多长(即：问以l和r结尾的字符串的公共后缀中，有多少个是原串的前缀,  
以及公共后缀与原串前缀的最大公共长度。)。

#### Input ####

第一行一个只包含小写字母的字符串S，代表被改过的提纲。注意字符串从1开始编号。  
第二行一个正整数m，即询问数。  
接下来m行，每行两个正整数l,r，即位置。

#### Output ####

共m行，每行两个正整数a,b，a表示有多少个合法字符串，b为最长合法字符串长度。

#### Sample Input ####

输入1：
    nguangdongren
    2
    5 13
    6 10
    输入2：
    ababbaabbaababab
    3
    14 16
    3 6
    2 4

#### Sample Output ####

输出1：
    1 1
    1 2
    输出2：
    2 4
    1 1
    1 2

#### Data Constraint ####

30%:|S|<=300;m<=300                                
60%: |S|<=3000;m<=100000                      
100%:|S|<=30000;m<=100000

# 分析 #

字符串前缀，我们可以想到KMP

然后我们就能想到，l的失配数组往前跳到第一个和r的适配数组往前跳到相同的，那个点就是它们最长公共前缀的点，然后能往前跳多少次就是公共前缀的个数

由于失配数组是一个数组，可以构成一个树的模型，就可以抽象成求LCA和LCA的深度了

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

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    using namespace std;
    const int N=3e4+10;
    struct Edge {
        int u,v,nx;
    }g[N];
    int list[N],cnt;
    string s;
    int m,len,f[N][20],dep[N];
    
    void KMP() {
        int next=0;
        f[1][0]=0;g[++cnt]=(Edge){
         0,1,list[0]};list[0]=cnt;
        for (int i=1;i<len;i++) {
            while (next!=0&&s[next]!=s[i]) next=f[next][0];
            if (s[next]==s[i]) next++;
            f[i+1][0]=next;
            g[++cnt]=(Edge){next,i+1,list[next]};list[next]=cnt;
        }
    }
    
    void DFS(int u) {
        for (int i=list[u];i;i=g[i].nx) dep[g[i].v]=dep[u]+1,DFS(g[i].v);
    }
    
    int LCA(int a,int b) {
        if (dep[a]<dep[b]) swap(a,b);
        for (int i=19;i>=0;i--) if (dep[f[a][i]]>=dep[b]) a=f[a][i];
        if (a==b) return a;
        for (int i=19;i>=0;i--) if (f[a][i]!=f[b][i]) a=f[a][i],b=f[b][i];
        return f[a][0];
    }
    
    int main() {
        cin>>s;
        len=s.length();
        KMP();
        DFS(0);
        for (int k=1;k<20;k++)
            for (int i=0;i<=len;i++) f[i][k]=f[f[i][k-1]][k-1];
        for (scanf("%d",&m);m;m--) {
            int l,r;
            scanf("%d%d",&l,&r);
            int lca=LCA(l,r);
            printf("%d %d\n",dep[lca],lca);
        }
    }

转载于:https://www.cnblogs.com/mastervan/p/10902418.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211215/5384552c00bb4c79aab52b328cd5e588.png