hdu 3068 최 장 답장 (manacher & 최 장 답장 문자열)
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7317 Accepted Submission(s): 2500
Problem Description
소문 자 영문 문자 a, b, c... y, z 로 만 구 성 된 문자열 S 를 보 여 줍 니 다. S 에서 가장 긴 답장 문자열 의 길 이 를 구 합 니 다.
답문 은 정반 독 이 모두 같은 문자열 이다. 예 를 들 어 aba, abba 등 이다.
Input
120 그룹 을 초과 하지 않 고 여러 그룹의 case 를 입력 하 십시오. 각 그룹 은 소문 자 영문 문자 a, b, c... y, z 로 구 성 된 문자열 S 를 입력 하 십시오.
두 그룹의 case 사 이 를 빈 줄 로 구분 합 니 다. (이 빈 줄 은 처리 할 필요 가 없습니다.)
문자열 길이 len < = 110000
Output
각 줄 의 정수 x 는 하나의 케이스 에 대응 하여 이 케이스 의 문자열 에 포 함 된 가장 긴 답장 길 이 를 표시 합 니 다.
Sample Input
aaaa
abab
Sample Output
4
3
Source
2009 Multi-University Training Contest 16 - Host by NIT
Recommend
lcy | We have carefully selected several similar problems for you: 1358 1686 3336 3065 3746
제목:
중국어 로 만나요.
생각:
manacher 누 드 문제.주로 연습 해 봐.manacher 알고리즘 설명 여기
사고방식 은 주로 문자열 에 격 리 부 호 를 붙 이 는 것 이다.회 문 열의 길 이 를 짝수 와 같 게 하여 기수 회 문 길 이 를 구하 다.모든 문 자 를 중심 으로 문자 의 최대 답장 길 이 를 구하 십시오.뒤의 결 과 는 앞의 결 과 를 이용한다.p [i] - 1 은 원본 문자열 의 길이 입 니 다.
자세 한 코드 참조:
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=111000;
int p[maxn<<1],len;
char buf[maxn],st[maxn<<1];
void init()
{
int i;
len=strlen(buf);
st[0]='$',st[1]='#';
for(i=0;i<len;i++)
st[2*i+2]=buf[i],st[2*i+3]='#';
len=2*len+2;
}
void manacher()
{
int i,id,mx=0;
for(i=1;i<len;i++)
{
p[i]=mx>i?min(mx-i,p[2*id-i]):1;
while(st[i+p[i]]==st[i-p[i]])// 。 st[0]='$'
p[i]++;
if(i+p[i]>mx)
mx=i+p[i],id=i;
}
}
int main()
{
int i,ans;
while(~scanf("%s",buf))
{
ans=1;
init();
manacher();
for(i=2;i<len;i++)
ans=max(ans,p[i]);
printf("%d
",ans-1);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Docker를 사용한 React 및 .NET Core 6.0 샘플 프로젝트 - 1부이 기사에서는 Entity Framework Core Code First 접근 방식을 사용하는 ASP.NET Core 6.0 WEP API의 CRUD(만들기, 읽기, 업데이트 및 삭제) 작업에 대해 설명합니다. 웹 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
