최 장 회 문 직렬 마차 알고리즘

길이 가 n 인 문자열 A 와 B 가 두 개 있 습 니 다.A 중에서 빈 문자열 A [l1... r1] 를 선택 할 수 있 습 니 다. B 중에서 빈 문자열 B [l2... r2] 를 선택 하여 r1 = l2 를 만족 시 킨 다음 에 이 를 조합 할 수 있 습 니 다 (A [l1... r1] + B [l2... r2]).이런 방법 으로 얻 을 수 있 는 가장 긴 회 문 꼬치 의 길 이 를 구하 세 요.주의: 본질 이 다른 답문 꼬치 갯 수 를 구 하 는 것 이 아 닙 니 다!!
문제 풀이 보고서: 두 개 사이 의 가장 긴 답장 문자열 을 찾 습 니 다. 단지 오후 내 내 끊 겼 을 뿐 입 니 다. 사실은 아주 간단 합 니 다. 말 라 차 를 두 번 달리 고 두 문자열 의 len 을 처리 합 니 다. a 문자열 의 마지막 점 을 매 거 하기 시 작 했 습 니 다. 여기 b 의 i - 2 는 a [i] 와 짝 을 이 루 었 습 니 다. 그들 사이 에 우리 가 이전에 추가 한 문 자 를 넣 었 기 때문에 tmp 로 그들의 최대 치 를 저장 합 니 다.왜 일 까요?일치 하 는 횟수 를 줄 이기 위해 서 입 니 다. 그 가 최대 치 일 때 일치 하지 않 아 도 괜 찮 습 니 다. 빈 꼬치 일 수 있 으 니까 요.

#include
using namespace std;
const	int N=100010;
char a[N],b[N],str[N*2],str2[N*2];
int len1[N*2],len2[N*2];
void get_str1(char a[])
{
	int k=0;
	str[k++]='@';
	for(int i=0;a[i];i++)
	{
		str[k++]='#';
		str[k++]=a[i]; 
	}
	str[k++]='#';
	str[k]=0;
}
void get_str2(char a[])
{
	int k=0;
	str2[k++]='@';
	for(int i=0;a[i];i++)
	{
		str2[k++]='#';
		str2[k++]=a[i]; 
	}
	str2[k++]='#';
	str2[k]=0;
}
void mlc(char a[])
{
	int id=0,mx=0;
	for(int i=1;a[i];i++)
	{
		len1[i]=mx>i?min(mx-i,len1[2*id-i]):1;
		while(a[i-len1[i]]==a[i+len1[i]])	len1[i]++;
		if(i+len1[i]>mx)
		{
			mx=i+len1[i];
			id=i;
		}
	}
}
void mlc2(char a[])
{
	int id=0,mx=0;
	for(int i=1;a[i];i++)
	{
		len2[i]=mx>i?min(mx-i,len2[2*id-i]):1;
		while(a[i-len2[i]]==a[i+len2[i]])	len2[i]++;
		if(i+len2[i]>mx)
		{
			mx=i+len2[i];
			id=i;
		}
	}
}
int main()
{
	int n;
	cin>>n;
	scanf("%s",a);
	scanf("%s",b);
	get_str1(a);
	get_str2(b);
	mlc(str);
	mlc2(str2);
	int ans=0;
	for(int i=2;str[i];i++)
	{
		int tmp=max(len1[i],len2[i-2]);
		while(str[i-tmp]==str2[i-2+tmp])	tmp++;
		ans=max(ans,tmp-1);
	}
	cout<<ans<<endl;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

HDU 3068 Manacher 모드 문제

클릭 하여 링크 열기 제목: 최 장 답장 문자열 구하 기 사고방식: Manacher 알고리즘 이 지나 가면 이 큰 소의 증명 서 를 추천 합 니 다....

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

최 장 회 문 직렬 마차 알고리즘

좋은 웹페이지 즐겨찾기