洛谷 P3181 [HAOI2016]找相同字符 题解【SAM】【前缀和】

作者: wjyyy 分类: 后缀自动机,字符串,解题报告 发布时间: 2019-03-30 16:02

点击量:57

SAM 挺神奇的,就是不会..

题目描述

给定两个字符串,求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。

输入格式

两行,两个字符串 $ s_1, s_2 $,长度分别为 $n_1, n_2$。字符串中只有小写字母。

输出格式

输出一个整数表示答案

输入样例

aabb
bbaa

输出样例

10

数据范围与约定

$1 \leq n_1, n_2 \leq 200000$

题解:

有两个长度均为 $2\times 10^5$ 级别的字符串,如果同时比较会相对耗费时间,因此考虑定一个研究另一个

因为字符串都比较长,排除 trie 后考虑构建 SAM。首先建立关于字符串 $s_1$ 的 SAM。

从起始节点开始,匹配字符串 $s_2$。设当前已经匹配的字符串长度为 $l$,则每匹配一次,令长度 $+1$。

当失配时,会跳到当前节点的 parent 树上的父亲去,直到存在这样的转移或到达了起始节点。

因为在 parent 树上,父亲是儿子的后缀。对于发现失配的节点,我们称之为 $k$,则 $mx[par[k]]<l\le mx[k]$。跳到父亲之后,最多只会匹配 $mx[par[k]]$ 个字符,因此 $l$ 总要对当前节点的 $mx$ 取较小值。

当我们从 $l-1$ 转移到 $l$ 时,字符串 $s_2$ 向后扩展一位,产生了 $l$ 个新的可匹配字符串,他们都是这个长为 $l$ 的字符串的后缀

后缀计数就比较简单了。由于 $l$ 一定大于它所有祖先的 $mx$,所以对于 $k$ 的所有祖先 $anc_i$,都会做出 $(mx[anc_i]-mx[fa[anc_i]])\times r_{anc_i}$ 的贡献 $b_{anc_i}$($r_k$ 表示 $k$ 的 $right$ 集合的大小),那么我们可以预处理出 parent 树上 $r$ 的前缀和,$k$ 做出的贡献就是根节点到它父亲上所有点的贡献 $b$,加上 $l\times r_{k}$。

时间复杂度 $O(n)$。

Code:

#include<cstdio>
#include<cstring>
#define ll long long
char s[200100],t[200100];
int ch[26][400100],mx[400100],r[400100],par[400100],pcnt;
void build()
{
    int p=pcnt=1;
    for(int i=1;s[i]!='\0';++i)
    {
        int w=s[i]-'a';
        int np=++pcnt;
        mx[np]=mx[p]+1;
        r[np]=1;
        while(p&&!ch[w][p])
        {
            ch[w][p]=np;
            p=par[p];
        }
        if(!p)
            par[np]=1;
        else
        {
            int q=ch[w][p];
            if(mx[q]==mx[p]+1)
                par[np]=q;
            else
            {
                int nq=++pcnt;
                mx[nq]=mx[p]+1;
                for(int j=0;j<26;++j)
                    ch[j][nq]=ch[j][q];
                while(p&&ch[w][p]==q)
                {
                    ch[w][p]=nq;
                    p=par[p];
                }
                par[nq]=par[q];
                par[q]=par[np]=nq;
            }
        }
        p=np;
    }
}
struct edge
{
    int n,nxt;
    edge(int n,int nxt)
    {
        this->n=n;
        this->nxt=nxt;
    }
    edge(){}
}e[400100];
int head[400100],ecnt=-1;
void add(int from,int to)
{
    e[++ecnt]=edge(to,head[from]);
    head[from]=ecnt;
}
void dfs(int x)
{
    for(int i=head[x];~i;i=e[i].nxt)
    {
        dfs(e[i].n);
        r[x]+=r[e[i].n];
    }
}
ll sum[400100];
void Dfs(int x)
{
    sum[x]+=(mx[x]-mx[par[x]])*r[x];
    for(int i=head[x];~i;i=e[i].nxt)
    {
        sum[e[i].n]+=sum[x];
        Dfs(e[i].n);
    }
}
int main()
{
    memset(head,-1,sizeof(head));
    scanf("%s",s+1);
    build();
    for(int i=2;i<=pcnt;++i)
        add(par[i],i);
    dfs(1);
    r[1]=0;
    Dfs(1);
    scanf("%s",t+1);
    int p=1;
    ll ans=0,len=0;
    for(int i=1;t[i]!='\0';++i)
    {
        while(p&&!ch[t[i]-'a'][p])
            p=par[p];
        if(!p)
        {
            p=1;
            len=0;
        }
        else
        {
            len=(mx[p]<len?mx[p]:len)+1;
            p=ch[t[i]-'a'][p];
        }
        //ans+=sum[par[p]]+r[p]*len[p];
        ans+=sum[par[p]]+r[p]*(len-mx[par[p]]);
    }
    printf("%lld\n",ans);
    return 0;
}

/*
aaaaaaaca
aaca

aacaacaabaacaacaa
acabaabaabaaca
*/

说点什么

avatar
  Subscribe  
提醒
/* */