【spoj LCS2】 Longest Common Substring II

时间:2022-08-30 12:49:35

http://www.spoj.com/problems/LCS2/ (题目链接)

题意

  求多个串的最长公共子串

Solution

  对其中一个串构造后缀自动机,然后其它串在上面跑匹配。对于每个串都可以跑出在SAM上的每一个节点的最长公共子串的长度,当然,有些节点虽然匹配时可能没有经过,但是在parent树上它的儿子却被经过了,作为儿子的后缀,那么这些节点显然也是被经过的,所以我们需要用parent树上的儿子节点去更新其父亲节点。完成之后,我们再对全局的匹配长度进行更新(取min)。

  爱神:对于SAM初学,要深刻理解出现次数向父亲传递,接收串数从儿子获取这句话。这里的父亲是parent树上的父亲,儿子是SAM图上的后继节点。

代码

// spoj LCS2
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<cstdio>
#include<cmath>
#include<set>
#define LL long long
#define inf 1<<30
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; const int maxn=100010;
char s[maxn]; namespace SAM {
int Dargen,sz,last,n;
int par[maxn<<1],len[maxn<<1],ch[maxn<<1][26],mat[maxn<<1],f[maxn<<1];
int b[maxn],id[maxn<<1];
void Extend(int c) {
int np=++sz,p=last;last=np;
len[np]=len[p]+1;
for (;p && !ch[p][c];p=par[p]) ch[p][c]=np;
if (!p) par[np]=Dargen;
else {
int q=ch[p][c];
if (len[q]==len[p]+1) par[np]=q;
else {
int nq=++sz;len[nq]=len[p]+1;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
par[nq]=par[q];
par[np]=par[q]=nq;
for (;p && ch[p][c]==q;p=par[p]) ch[p][c]=nq;
}
}
}
void build() {
last=sz=Dargen=1;
n=strlen(s+1);
for (int i=1;i<=n;i++) Extend(s[i]-'a');
}
void pre() {
for (int i=1;i<=sz;i++) b[len[i]]++;
for (int i=1;i<=n;i++) b[i]+=b[i-1];
for (int i=1;i<=sz;i++) id[b[len[i]]--]=i;
for (int i=1;i<=sz;i++) mat[i]=inf;
}
void match() {
int n=strlen(s+1);
int ll=0;
for (int i=1;i<=sz;i++) f[i]=0;
for (int p=Dargen,i=1;i<=n;i++) {
while (p>1 && !ch[p][s[i]-'a']) p=par[p],ll=len[p];
if (ch[p][s[i]-'a']) {
p=ch[p][s[i]-'a'];
f[p]=max(f[p],++ll);
}
}
for (int i=sz;i>=1;i--)
if (f[id[i]]) f[par[id[i]]]=len[par[id[i]]];
for (int i=1;i<=sz;i++) mat[i]=min(mat[i],f[i]);
}
int query() {
int ans=0;
for (int i=1;i<=sz;i++) ans=max(ans,mat[i]);
return ans;
}
}
using namespace SAM; int main() {
scanf("%s",s+1);
build();
pre();
while (scanf("%s",s+1)!=EOF) match();
printf("%d",query());
return 0;
}

【spoj LCS2】 Longest Common Substring II的更多相关文章

  1. 【SPOJ - LCS2】Longest Common Substring II【SAM】

    题意 求出多个串的最长公共子串. 分析 刚学SAM想做这个题的话最好先去做一下那道codevs3160.求两个串的LCS应该怎么求?把一个串s1建自动机,然后跑另一个串s2,然后找出s2每个前缀的最长 ...

  2. 【SPOJ 1812】Longest Common Substring II

    http://www.spoj.com/problems/LCS2/ 这道题想了好久. 做法是对第一个串建后缀自动机,然后用后面的串去匹配它,并在走过的状态上记录走到这个状态时的最长距离.每匹配完一个 ...

  3. 【SPOJ】Longest Common Substring II (后缀自动机)

    [SPOJ]Longest Common Substring II (后缀自动机) 题面 Vjudge 题意:求若干个串的最长公共子串 题解 对于某一个串构建\(SAM\) 每个串依次进行匹配 同时记 ...

  4. 【SPOJ】Longest Common Substring II

    [SPOJ]Longest Common Substring II 多个字符串求最长公共子串 还是将一个子串建SAM,其他字符串全部跑一边,记录每个点的最大贡献 由于是所有串,要对每个点每个字符串跑完 ...

  5. 【hdu 1403】Longest Common Substring

    [链接]h在这里写链接 [题意] 求两个串的最长公共子串. [题解] Sa[i]表示的是字典序为i的后缀的起始位置. 可以把两个字符串合在一起(中间用一个比'z'大的字符分割); 则如果Sa[i-1] ...

  6. 【SP1812】LCS2 - Longest Common Substring II

    [SP1812]LCS2 - Longest Common Substring II 题面 洛谷 题解 你首先得会做这题. 然后就其实就很简单了, 你在每一个状态\(i\)打一个标记\(f[i]\)表 ...

  7. SPOJ1812 LCS2 - Longest Common Substring II【SAM LCS】

    LCS2 - Longest Common Substring II 多个字符串找最长公共子串 以其中一个串建\(SAM\),然后用其他串一个个去匹配,每次的匹配方式和两个串找\(LCS\)一样,就是 ...

  8. 【SPOJ】Longest Common Substring(后缀自动机)

    [SPOJ]Longest Common Substring(后缀自动机) 题面 Vjudge 题意:求两个串的最长公共子串 题解 \(SA\)的做法很简单 不再赘述 对于一个串构建\(SAM\) 另 ...

  9. spoj 1812 LCS2 - Longest Common Substring II &lpar;后缀自己主动机&rpar;

    spoj 1812 LCS2 - Longest Common Substring II 题意: 给出最多n个字符串A[1], ..., A[n], 求这n个字符串的最长公共子串. 限制: 1 &lt ...

随机推荐

  1. java基础(二十二)线程

    这里有我之前上课总结的一些知识点以及代码大部分是老师讲的笔记 个人认为是非常好的,,也是比较经典的内容,真诚的希望这些对于那些想学习的人有所帮助! 由于代码是分模块的上传非常的不便.也比较多,讲的也是 ...

  2. System&period;getProperty&lpar;&rpar;的用途

     偶尔用到 System.getProperty(),找起来也不方便.这里做下记录备忘: 编写的测试类: public class TestSystemproperty { public stat ...

  3. php的运行流程

    1.Zend引擎:Zend整体用纯C实现,是PHP的内核部分,他将PHP代码翻译(词法.语法解析等一系列编译过程)为可执行opcode的处理并实现相应的处理方法.实现了基本的数据结构(如:hashta ...

  4. 翻译:用户变量&lpar;User-Defined Variable&rpar;(已提交到MariaDB官方手册)

    本文为mariadb官方手册:User-Defined Variables的译文. 原文:https://mariadb.com/kb/en/user-defined-variables/我提交到Ma ...

  5. java 基础 instance of

    a instance of b   a是否是b类的实例对象 返回 bool值

  6. 【linux】linux下对java程序生成dump文件,并使用IBM Heap Analyzer进行分析,查找定位内存泄漏的问题代码

    1.首先,java程序启动在linux,怎么生成dump文件? 1>第一步,首先你需要得到java程序的PID,最简单的方法使用如下命令 ps -ef|grep java 或者如果是docker ...

  7. 朽木第一至三季&sol;全集Deadwood迅雷下载

    英文译名Deadwood,第1-3季(2004-2006)HBO. 本季看点:<朽木>又名<死木>由<纽约重案组>(NYPD Blue)制作人大卫·米奇担纲,讲述美 ...

  8. Linux新建用户 useradd&amp&semi;groupadd

    建立一个新组,并设置组ID加入系统:#groupadd -g 1000 sparkgroup #useradd -u 2000 -g sparkgroup sparkuser #mkdir -p /a ...

  9. MySQL,SQLSERVER,ORACLE获取数据库表名及字段名

    1.MySQL 获取表名: 用“show tables”命令.在程序中也可以采用该命令获取,在返回的RowSet中的“Tables_in_db”读出来.其中“db”是指你的数据库的名称,比如说Tabl ...

  10. Java 设计模式系列(十七)中介者模式

    Java 设计模式系列(十七)中介者模式 用一个中介对象来封装一系列的对象交互.中介者使得各对象不需要显式地相互引用,从而使其耦合松散,而且可以独立的改变它们之间的交互 一.中介者模式结构 Media ...