HDU 4513 퍼 펙 트 대형 II (Manacher)
이 안 은 정상 적 으로 가장 긴 회 문 꼬치 를 구 하 는 것 과 달리 이 회 문 꼬치 는 앞부분 이 단 조 롭 게 증가 해 야 한다. 물론 대칭 성 으로 인해 후반 부분 이 단 조 롭 게 감소 해 야 한다!
그러면 원래 의 기초 위 에 몇 가지 판단 을 더 해서 답장 꼬치 가 상기 요 구 를 만족 시 킬 수 있 도록 해 야 한다.
먼저, 가장 오른쪽 은 sign 의 위치 에 있 습 니 다. 그러면 가장 긴 회 문 꼬치 길 이 를 1 로 늘 려 야 합 니 다. 이것 은 분명 하고 대칭 적 입 니 다.
그 다음 에 회 문 꼬치 데이터 의 위치 라면 가장 오른쪽 이나 가장 왼쪽 에서 2 를 줄 이거 나 2 를 더 해서 요 구 를 만족 시 키 는 지 비교 해 야 한다.여기 에는 두 가지 가능성 이 있 습 니 다. 만약 에 현재 의 숫자 가 데이터 라면 데이터 의 크기 를 판단 해 야 합 니 다. 그러나 sign 이 라면 가장 오른쪽 에 있 는 위치 에서 2 를 줄 이 는 위치 가 어디 에 있 는 지 판단 해 야 합 니 다. 현재 위치의 오른쪽 에 있 을 수 있 습 니 다. 원래 의 문자열 에 이런 하위 문자열 이 있 는 것 과 같 습 니 다. '23 23' 이 라면 당연히 1 을 추가 해 야 합 니 다.그리고 다음은 더 확 장 된 데이터 의 크기 를 판단 해 야 한다.
그림 을 그리 면 모두 이 세 가지 가능성 을 발견 할 수 있 습 니 다. 특히 sign 양쪽 의 똑 같은 데 이 터 는 잘 고려 해 야 할 것 같 습 니 다. 빠 뜨 려 서 는 안 됩 니 다.
코드:
//
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100100;
int T, n, id, Maxl, Maxid, p[N<<1];
int s[N], str[N<<1];
void kp() {
for ( int i = 1; i < n; ++i ) {
if ( Maxid > i ) p[i] = min( Maxid-i, p[id*2-i] );
else p[i] = 1;
while ( str[i+p[i]] == str[i-p[i]] ) {
if ( str[i+p[i]] == 2 ) p[i]++;
else if ( ( i+p[i]-2 < i ) || str[i+p[i]] <= str[i+p[i]-2] ) p[i]++;
else break;
}
if ( Maxid < p[i] + i ) {
Maxid = p[i]+i;
id = i;
}
if ( p[i] > Maxl ) Maxl = p[i];
}
}
int main()
{
while ( scanf("%d", &T) != EOF ) {
while ( T-- ) {
scanf("%d", &n);
memset( str, 0, sizeof(str) );
str[0] = -1; str[1] = 2;
int j = 2;
for ( int i = 0; i < n; ++i ) {
scanf("%d", &str[j++]);
str[j++] = 2;
}
n = j; str[n] = -2;
//printf("%d
", n);
//for ( int i = 0; i < n; ++i ) printf(" %d", str[i]);
id = Maxid = Maxl = 0;
kp();
printf("%d
", Maxl - 1);
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
