SPOJ LCS(Longest Common Substring - 접미사 로봇 - 결점의 Parent 포함 관계)
3434 단어 substring
1811. Longest Common Substring Problem code: 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
이 문제는 LCS 문자열 2개가 필요합니다.
그러면 먼저 A열을 읽은 다음에 A열에 B열을 매칭하면 분명히
그러나 하나의 결점이 표시할 수 있는 접미사는 |maxS|-|minS|+1개입니다.
그러면 이렇게
현재 결점 x에 있다고 가정하면 다음 B열이 일치할 알파벳은 c이다
만약 x에ch[c]가 있다면, 걸어가면 len+1
그렇지 않으면 pre를 찾아서 len=pre의 maxS를 업데이트합니다
이유는 다음과 같습니다.
원래 문자열 설정=ababd,babd,abd 중 하나로 일치
abdx가 존재하지 않아서 일치할 수 없습니다.
pre=bd, d를 가져옵니다. (정의에 의하면 'dc가 일치하고 bdc가 존재하지 않음' 이 존재하지 않기 때문에 둘 다 1개의 상태가 될 수 있습니다.)
그러면 len=pre의 maxS(step)
그렇지 않으면 루트를 되돌려줍니다,len=0
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Lson (x<<1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define MAXN (500000+10)
long long mul(long long a,long long b){return (a*b)%F;}
long long add(long long a,long long b){return (a+b)%F;}
long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;}
typedef long long ll;
char s1[MAXN],s2[MAXN];
struct node
{
int pre,step,ch[26];
char c;
node(){pre=step=c=0;memset(ch,sizeof(ch),0);}
}a[MAXN];
int last=0,total=0;
void insert(char c)
{
int np=++total;a[np].c=c+'a',a[np].step=a[last].step+1;
int p=last;
for(;!a[p].ch[c];p=a[p].pre) a[p].ch[c]=np;
if (a[p].ch[c]==np) a[np].pre=p;
else
{
int q=a[p].ch[c];
if (a[q].step>a[p].step+1)
{
int nq=++total;a[nq]=a[q];a[nq].step=a[p].step+1;
a[np].pre=a[q].pre=nq;
for(;a[p].ch[c]==q;p=a[p].pre) a[p].ch[c]=nq;
}else a[np].pre=q;
}
last=np;
}
int main()
{
// freopen("spojLCS.in","r",stdin);
scanf("%s%s",s1+1,s2+1);int n=strlen(s1+1),m=strlen(s2+1);
For(i,n) insert(s1[i]-'a');
int now=0,ans=0,len=0;
For(i,m)
{
char c=s2[i]-'a';
while (now&&!a[now].ch[c]) now=a[now].pre,len=a[now].step;
if (a[now].ch[c]) now=a[now].ch[c],len++;
ans=max(ans,len);
}
printf("%d
",ans);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
가장 많이 나타나는 오류 - 1주차예를 들면 다음 코드를 실행하면 바로 이 오류가 뜬다. 오류 발생 이유: iterable 객체 자리에 정수형 자료(int)를 입력했기 때문. C++처럼 10을 넣으면 10번을 반복해준다는게 아니다. iterable ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.