2946: [Poi2000]公共串
Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 787 Solved: 342
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
abcb
bca
acbc
Sample Output
HINT
Source
求若干字符串的最长公共子串。
和SPOJ的那道题简直一模一样,后缀自动机。
#include <bits/stdc++.h> const int maxn = 5e5 + ; /* AUTOMATON */ int last;
int tail;
int mini[maxn];
int maxi[maxn];
int step[maxn];
int fail[maxn];
int next[maxn][]; inline void buildAutomaton(char *s)
{
last = ;
tail = ;
while (*s)
{
int c = *s++ - 'a';
int p = last;
int t = tail++;
step[t] = step[p] + ;
mini[t] = maxi[t] = step[t];
while (p && !next[p][c])
next[p][c] = t, p = fail[p];
if (p)
{
int q = next[p][c];
if (step[q] == step[p] + )
fail[t] = q;
else
{
int k = tail++;
fail[k] = fail[q];
fail[q] = fail[t] = k;
step[k] = step[p] + ;
mini[k] = maxi[k] = step[k];
for (int i = ; i < ; ++i)
next[k][i] = next[q][i];
while (p && next[p][c] == q)
next[p][c] = k, p = fail[p];
}
}
else
fail[t] = ;
last = t;
}
} inline void searchAutomaton(char *s)
{
memset(maxi, , sizeof(maxi));
for (int t = , k = ; *s; )
{
int c = *s++ - 'a';
if (next[t][c])
++k, t = next[t][c];
else
{
while (t && !next[t][c])
t = fail[t];
if (t)
k = step[t] + , t = next[t][c];
else
k = , t = ;
}
if (maxi[t] < k)
maxi[t] = k;
}
for (int i = tail - ; i; --i)
if (maxi[fail[i]] < maxi[i])
maxi[fail[i]] = maxi[i];
for (int i = ; i < tail; ++i)
if (mini[i] > maxi[i])
mini[i] = maxi[i];
} inline int calculateAutomaton(void)
{
register int ret = ;
for (int i = ; i < tail; ++i)
if (ret < mini[i])
ret = mini[i];
return ret;
} /* MAIN FUNC */ char str[maxn]; signed main(void)
{
int n;
scanf("%d", &n);
scanf("%s", str);
buildAutomaton(str);
for (int i = ; i < n; ++i)
scanf("%s", str), searchAutomaton(str);
printf("%d\n", calculateAutomaton());
}
@Author: YouSiki
BZOJ 2946: [Poi2000]公共串的更多相关文章
-
BZOJ 2946: [Poi2000]公共串( 后缀自动机 )
一个串建后缀自动机, 其他串在上面跑, 然后用当前串跑的去更新全部 ------------------------------------------------------------------ ...
-
bzoj 2946 [Poi2000]公共串——后缀自动机
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=2946 对每个串都建一个后缀自动机,然后 dfs 其中一个自动机,记录同步的话在别的自动机上走 ...
-
BZOJ 2946 [Poi2000]公共串 (二分+Hash/二分+后缀数组/后缀自动机)
求多串的最长公共字串. 法1: 二分长度+hash 传送门 法2: 二分+后缀数组 传送门 法3: 后缀自动机 拿第一个串建自动机,然后用其他串在上面匹配.每次求出SAM上每个节点的最长匹配长度后,再 ...
-
BZOJ 2946 POI2000 公共串 后缀自动机(多串最长公共子串)
题意概述:给出N个字符串,每个串的长度<=2000(雾...可能是当年的年代太久远机子太差了),问这N个字符串的最长公共子串长度为多少.(N<=5) 抛开数据结构,先想想朴素做法. 设计一 ...
-
BZOJ 2946 [Poi2000]公共串 ——后缀自动机
任意选择一个串作为模式串,构建出后缀自动机. 然后用其他的串在后缀自动机上跑匹配. 然后就到了理解后缀自动机性质的时候. 在某一个节点的最大值是可以沿着parent树上传的. 然后用dp[i][j]表 ...
-
bzoj 2946: [Poi2000]公共串【SAM】
对第一个串建SAM,把剩下的串在上面跑,每次跑一个串的时候在SAM的端点上记录匹配到这的最大长度,然后对这些串跑的结果取min,然后从这些节点的min中取max就是答案 注意在一个点更新后它的祖先也会 ...
-
【BZOJ 2946】 2946: [Poi2000]公共串 (SAM)
2946: [Poi2000]公共串 Time Limit: 3 Sec Memory Limit: 128 MBSubmit: 1063 Solved: 469 Description ...
-
【BZOJ】2946: [Poi2000]公共串
http://www.lydsy.com/JudgeOnline/problem.php?id=2946 题意:给n个串,求最大公共子串.(1<=n<=5,每个串长度<=2000) ...
-
BZOJ_2946_[Poi2000]公共串_后缀数组+二分答案
BZOJ_2946_[Poi2000]公共串_后缀数组+二分答案 Description 给出几个由小写字母构成的单词,求它们最长的公共子串的长度. 任务: l 读入单 ...
随机推荐
-
UIRefreshControl
在iOS6中UITableViewController 已经集成了UIRefreshControl 控件.UIRefreshControl目前只能用于UITableViewController
-
PHP使用Mysql事务
<?php //数据库连接 $conn = mysql_connect('localhost', 'root', ''); mysql_select_db('test', $conn); mys ...
-
[转]利于ThreadLocal管理Hibernate Session
摘自http://aladdin.iteye.com/blog/40986 在利用Hibernate开发DAO模块时,我们和Session打的交道最多,所以如何合理的管理Session,避免Sessi ...
-
unity3d游戏无法部署到windows phone8手机上的解决方法
今天搞了个unity3d游戏,准备部署到自己的lumia 920上,数据线连接正常,操作正常,但是“build”以后,始终无法部署到手机上,也没有在选择的目录下生产任何相关文件.(你的系统必须是win ...
-
Google高级技巧—google Hack★★★★
google hacking事实上并算不上什么新东西,当时并没有重视这样的技术,觉得webshell什么的,并无太大实际用途.google hacking事实上并非如此简单... 经常使用的googl ...
-
xampp安装时mysql报错
问题描述:以前安装过mysql,后来安装xampp,mysql打不开,出错提示16:04:48 [mysql] MySQL Service detected with wrong path16:0 ...
-
关于php输入$_post[‘’]报错的原因
在php中输入$_post[‘’]值时页面报错,是因为变量未声明,所以页面出现提示Undefined index,是因为首先要用isset来判断是否存在这个变量. 如:isset($_POST['/* ...
-
Python的路径引用
1.以HOME目录为准,进行跳转 sys.path.append(os.path.dirname(__file__) + os.sep + '../') from config import swor ...
-
PHP文件管理—实现网盘以及压缩包的功能操作
代码如下: 1.主页面file_zip.php <!DOCTYPE html> <html> <head> <meta charset="UTF-8 ...
-
vue的单向数据流
父级向子组件传递的值, 子组件不能直接修改这个穿过来的值,否则会曝出警告,这就是单项数据流. 如果是引用值,传递的是引用值得地址,而不是值本身,也就是说,子组件里修改这个传过来的值,通常的做法是放到它 ...