【bzoj2946】[Poi2000]公共串 后缀自动机

时间:2022-08-27 14:58:38

[Poi2000]公共串

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 1386  Solved: 620
[Submit][Status][Discuss]

Description

 
       给出几个由小写字母构成的单词,求它们最长的公共子串的长度。
任务:
l        读入单词
l        计算最长公共子串的长度
l        输出结果
 

Input

 
文件的第一行是整数 n,1<=n<=5,表示单词的数量。接下来n行每行一个单词,只由小写字母组成,单词的长度至少为1,最大为2000。
 

Output

仅一行,一个整数,最长公共子串的长度。
 

Sample Input

3
abcb
bca
acbc

Sample Output

HINT

后缀自动机

 #include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> #define N 2007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
} int n;
char ch[N]; struct SAM
{
int cnt,last;
int fa[],a[][],mx[],len[],ans[];
int v[],q[];
SAM(){last=++cnt;}
void extend(int c)
{
int p=last,np=last=++cnt;mx[np]=mx[p]+;
while(!a[p][c]&&p)a[p][c]=np,p=fa[p];
if(!p)fa[np]=;
else
{
int q=a[p][c];
if(mx[p]+==mx[q])fa[np]=q;
else
{
int nq=++cnt;mx[nq]=mx[p]+;
memcpy(a[nq],a[q],sizeof(a[q]));
fa[nq]=fa[q];
fa[np]=fa[q]=nq;
while(a[p][c]==q)a[p][c]=nq,p=fa[p];
}
}
}
void pre()
{
for(int i=;i<=cnt;i++)ans[i]=mx[i];
for(int i=;i<=cnt;i++)v[mx[i]]++;
for(int i=;i<=cnt;i++)v[i]+=v[i-];
for(int i=cnt;i;i--)q[v[mx[i]]--]=i;
}
void solve()
{
scanf("%s",ch+);
memset(len,,sizeof(len));
int l=strlen(ch+),p=,tmp=;
for(int i=;i<=l;i++)
{
int c=ch[i]-'a';
while(!a[p][c]&&p)p=fa[p];
if(p==)p=,tmp=;
else tmp=min(tmp,mx[p])+,p=a[p][c];
len[p]=max(len[p],tmp);
}
for(int i=cnt;i;i--)len[fa[q[i]]]=max(len[fa[q[i]]],len[q[i]]);
for(int i=;i<=cnt;i++)ans[i]=min(ans[i],len[i]);
}
}sam;
int main()
{
n=read();scanf("%s",ch+);
int l=strlen(ch+);
for(int i=;i<=l;i++)sam.extend(ch[i]-'a');
sam.pre();
for(int i=;i<n;i++)sam.solve();
int ans=;
for(int i=;i<=sam.cnt;i++)
ans=max(ans,sam.ans[i]);
printf("%d\n",ans);
}

【bzoj2946】[Poi2000]公共串 后缀自动机的更多相关文章

  1. BZOJ2946 &lbrack;Poi2000&rsqb;公共串&lpar;后缀自动机&rpar;

    Description          给出几个由小写字母构成的单词,求它们最长的公共子串的长度. 任务: l        读入单词 l        计算最长公共子串的长度 l        输 ...

  2. BZOJ 2946&colon; &lbrack;Poi2000&rsqb;公共串&lpar; 后缀自动机 &rpar;

    一个串建后缀自动机, 其他串在上面跑, 然后用当前串跑的去更新全部 ------------------------------------------------------------------ ...

  3. bzoj 2946 &lbrack;Poi2000&rsqb;公共串——后缀自动机

    题目:https://www.lydsy.com/JudgeOnline/problem.php?id=2946 对每个串都建一个后缀自动机,然后 dfs 其中一个自动机,记录同步的话在别的自动机上走 ...

  4. BZOJ 2946 &lbrack;Poi2000&rsqb;公共串 ——后缀自动机

    任意选择一个串作为模式串,构建出后缀自动机. 然后用其他的串在后缀自动机上跑匹配. 然后就到了理解后缀自动机性质的时候. 在某一个节点的最大值是可以沿着parent树上传的. 然后用dp[i][j]表 ...

  5. BZOJ 2946 POI2000 公共串 后缀自动机(多串最长公共子串)

    题意概述:给出N个字符串,每个串的长度<=2000(雾...可能是当年的年代太久远机子太差了),问这N个字符串的最长公共子串长度为多少.(N<=5) 抛开数据结构,先想想朴素做法. 设计一 ...

  6. 【BZOJ2946】&lbrack;Poi2000&rsqb;公共串 后缀数组&plus;二分

    [BZOJ2946][Poi2000]公共串 Description        给出几个由小写字母构成的单词,求它们最长的公共子串的长度. 任务: l        读入单词 l        计 ...

  7. &lbrack;POI2000&rsqb; 公共串 - 后缀数组&comma;二分

    [POI2000] 公共串 Description 给出几个由小写字母构成的单词,求它们最长的公共子串的长度. Solution 预处理出后缀数组和高度数组,二分答案 \(k\) ,对于每一个连续的 ...

  8. BZOJ2946 Poi2000 公共串 【后缀自动机】

    Description 给出几个由小写字母构成的单词,求它们最长的公共子串的长度. 任务: l 读入单词 l 计算最长公共子串的长度 l 输出结果 Input 文件的第一行是整数 n,1<=n& ...

  9. &lbrack;bzoj2946&rsqb;&lbrack;Poi2000&rsqb;公共串&lowbar;后缀数组&lowbar;二分

    公共串 bzoj-2946 Poi-2000 题目大意:给定$n$个字符串,求他们的最长公共子串. 注释:$1\le n\le 5$,$1\le minlen<maxlen\le 2000$. ...

随机推荐

  1. Html标签第二课css

    css(Cascading Style Sheet)叠层样式表.用于控制网页样式并允许将样式信息与网页内容分离的一种标记性语言. 一:样式三种控制方法 1.行内样式: <div  style=& ...

  2. scp 在Ubuntu下传文件 基于ssh

    scp是linux下的远程拷贝 命令: (1)将本地文件拷贝到远程:scp  文件名 用户名@计算机IP或者计算机名称:远程路径  (2)从远程将文件拷回本地:scp  用户名@计算机IP或者计算机名 ...

  3. App开放接口api安全性—Token签名sign的设计与实现

    前言 在app开放接口api的设计中,避免不了的就是安全性问题,因为大多数接口涉及到用户的个人信息以及一些敏感的数据,所以对这些接口需要进行身份的认证,那么这就需要用户提供一些信息,比如用户名密码等, ...

  4. std&colon;&colon;string 字符替换函数

    // 替换路径中所有“\”为“/” #include <algorithm> static std::string ConvertSlash(std::string& strUrl ...

  5. reduce&sol;filter&sol;map&sol;zip&sol;isinstance&sol;list列表推导式

  6. spring启动component-scan类扫描加载过程&lpar;转&rpar;

    文章转自 http://www.it165.net/pro/html/201406/15205.html 有朋友最近问到了 spring 加载类的过程,尤其是基于 annotation 注解的加载过程 ...

  7. awk 详解

    AWK 简介 AWK是一种优良的文本处理工具.它不仅是 Linux 中也是任何环境中现有的功能最强大的数据处理引擎之一.这种编程及数据操作语言(其名称得自于它的创始人 Alfred Aho .Pete ...

  8. caffe 中solver&period;prototxt

    关于cifar-10和mnist的weight_decay和momentum也是相当的重要:就是出现一次把cifar-10的两个值直接用在mnist上,发现错误很大.

  9. bzoj 2119 股市的预测——枚举长度的关键点&plus;后缀数组

    题目:https://www.lydsy.com/JudgeOnline/problem.php?id=2119 就是找差分序列上中间差 m 的相等的两段. 考虑枚举这样一段的长度 L .可以把序列分 ...

  10. 二级域名 cookie session 共享

    setcookie('login','12345',0,'/','.abc.com'); session_set_cookie_params(0,'/','.abc.com');session_sta ...