spoj 1811 LCS 后缀自动机

2024-03-30 16:32
文章标签 后缀 lcs 自动机 spoj 1811

本文主要是介绍spoj 1811 LCS 后缀自动机,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

A string is finite sequence of characters over a non-empty finite set Σ.
In this problem, Σ is the set of lowercase letters.
Substring, also called factor, is a consecutive sequence of characters occurrences at least once in a string.
Now your task is simple, for two given strings, find the length of the longest common substring of them.
Here common substring means a substring of two or more strings.
Input
The input contains exactly two lines, each line consists of no more than 250000 lowercase letters, representing a string.
Output
The length of the longest common substring. If such string doesn’t exist, print “0” instead.
Example
Input:
alsdfkjfjkdsal
fdjskalajfkdsla

Output:
3
Notice: new testcases added


传送门
题意:给出两个串,求它们的最长公共子串。
本来其实是想着后缀数组做的。。
然后就看见评论里说”suffix array will not work”
吓尿了……百度后才发现这题O(NlogN)要被卡!噗。。
好吧只好用自动机做了。
我对后缀自动机感觉理解欠一点,
这题也想了好久。。
主要就是:DAG,
还有parent树的种种性质(一个点的pre(或者说parent)结点,
右端点集合>这个点的右端点集合,所以长度肯定更短)
说不大清楚,建议自己去学学(=v=)
那么如何求LCS呢?首先在自动机上,有当前ch的边,
就往那边走,
不然肯定要退回到某一个部分,具体就是一个点p,
这个部分,满足后缀与当前匹配到的一致,
且有ch的边(如果没有这种点的话直接回到root去重新开始就好了)
那么长度更新成step[p]+1,并且走它的ch儿子。
中途不停更新ans的最大值即可。

这个比较好理解。因为后缀部分一定匹配了,
那么最长公共子串一定建立在某部分匹配的基础上,
parent树就是这么nb……

注意啦sam的数组开2倍(最多2n-1个点)

#include<bits/stdc++.h>
using namespace std;
const int N=250005;
int tot;
struct SAM{int last,step[N<<1],pre[N<<1];int son[N<<1][26];SAM(){last=1;memset(son,0,sizeof(son));memset(pre,0,sizeof(pre));memset(step,0,sizeof(step));}void insert(int c){int p=last,np=++tot;step[np]=step[p]+1;for (;p && !son[p][c];p=pre[p]) son[p][c]=np;if (!p) pre[np]=1;else{int q=son[p][c];if (step[p]+1!=step[q]){int nq=++tot;step[nq]=step[p]+1;memcpy(son[nq],son[q],sizeof(son[nq]));pre[nq]=pre[q];pre[q]=pre[np]=nq;for (;son[p][c]==q;p=pre[p]) son[p][c]=nq;} else pre[np]=q;}last=np;}
}sam;
int main(){char s[N];scanf("%s",s+1);int n=strlen(s+1);tot=1;for (int i=1;i<=n;i++) sam.insert(s[i]-'a');scanf("%s",s+1);n=strlen(s+1);int ans=0,len=0,p=1;for (int i=1;i<=n;i++){if (sam.son[p][s[i]-'a'])len++,p=sam.son[p][s[i]-'a'];else{for (;p && !sam.son[p][s[i]-'a'];p=sam.pre[p]);if (!p) len=0,p=1;else len=sam.step[p]+1,p=sam.son[p][s[i]-'a'];}ans=max(ans,len);}printf("%d\n",ans);return 0;
}

这篇关于spoj 1811 LCS 后缀自动机的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/861994

相关文章

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

uva 10066 LCS

题意: 最长公共子序列。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <queue>#include

hdu 3065 AC自动机 匹配串编号以及出现次数

题意: 仍旧是天朝语题。 Input 第一行,一个整数N(1<=N<=1000),表示病毒特征码的个数。 接下来N行,每行表示一个病毒特征码,特征码字符串长度在1—50之间,并且只包含“英文大写字符”。任意两个病毒特征码,不会完全相同。 在这之后一行,表示“万恶之源”网站源码,源码字符串长度在2000000之内。字符串中字符都是ASCII码可见字符(不包括回车)。

POJ 1625 自动机

给出包含n个可见字符的字符集,以下所提字符串均由该字符集中的字符构成。给出p个长度不超过10的字符串,求长为m且不包含上述p个字符串的字符串有多少个。 g++提交 int mat[108][108] ;int matn ;int N ;map<char ,int> to ;//ACconst int maxm = 108 ;const int kin

zoj 3228 ac自动机

给出一个字符串和若干个单词,问这些单词在字符串里面出现了多少次。单词前面为0表示这个单词可重叠出现,1为不可重叠出现。 Sample Input ab 2 0 ab 1 ab abababac 2 0 aba 1 aba abcdefghijklmnopqrstuvwxyz 3 0 abc 1 def 1 jmn Sample Output Case 1 1 1 Case 2

将浮点型算式的中缀表达式转换成后缀表达式并算出式子结果

最近因为需要了解如何将在Win应用程序控制台输入的算式表达式转化成其后缀表达式的算法,所以在网上搜索了一下,看到许多人的程序都只是对应于运算数在0~9的范围内的整型运算式,所以自己就写了一个可以计算浮点型算式的程序,一下是运行时的截图: 式子中的a,b,c是可供用户自行输入的变量。 首先,我先对输入的运算符进行了简单的合法性判断,我的判断代 码如下: //函数的传入参

正规式与有限自动机例题

答案:D 知识点: 正规式 正规集 举例 ab 字符串ab构成的集合 {ab} a|b 字符串a,b构成的集合 {a,b} a^* 由0或者多个a构成的字符串集合 {空,a,aa,aaa,aaaa····} (a|b)^* 所有字符a和b构成的串的集合 {空,a,b,ab,aab,aba,aaab····} a(a|b)^* 以a为首字符的a,b字符串的集

后缀表达式转中缀表达式

假定有后缀表达式1 2 3 + 4 * +5 – ,请将它转化为前缀表达式。 利用表达式树: 1.从左到右扫面后缀表达式,一次一个符号读入表达式。2.如果符号是操作数,那么就建立一个单节点树并将它推入栈中。如果符号是操作符,那么就从栈中弹出两个树T1和T2(T1先弹出)并形成一颗新的树,该树的根就是操作符,它的左、右儿子分别是T2和T1(先出的为右子树,后出的为左子树)。然后将指向这棵新树的指

什么是顶级域名后缀?

在互联网发展的历程中,顶级域名(Top-Level Domain,简称TLD)扮演着至关重要的角色。而这些顶级域名的后缀,则更是成为了整个网络世界的分类标准和识别依据。 顶级域名后缀,通常指位于域名最右端的部分,如".com"、“.org”、".cn"等。它们为下层的二级域名和三级域名提供了一个基础的分类框架,让互联网上的各类网站、组织和个人能够根据自身特点选择合适的域名后缀。 不同类型的顶级

NLP文本相似度之LCS

基础 LCS(Longest Common Subsequence)通常指的是最长公共子序列,区别最长公共字串(Longest Common Substring)。我们先从子序列的定义理解: 一个序列S任意删除若干个字符得到新的序列T,则T叫做S的子序列。 子序列和子串的一个很大的不同点是,子序列不要求连接,而子串要求连接。 两个序列X和Y的公共子序列中,长度最长的那个,定义为X和Y