HDU 3068 - 최 장 답문 - O (n) 시간 최 장 답문 하위 문자열 구하 기

4
3

 
 
제목: 문자열 을 하나 드 리 겠 습 니 다. 이 문자열 에서 가장 긴 답장 문자열 을 구 해 주세요.
 
생각:
방법 1: 가장 간단 한 사고, 하위 문자열 의 출발점 과 종점 을 매 거 하지만 이 문제 에 있어 서 는 의심 할 여지없이 시간 을 초과 합 니 다!
방법 2: 리 턴 문자열 의 중간 위 치 를 매 거 하고 유 여 가 의 알고리즘 책 을 보 며 매 거 코드 는 다음 과 같다.

#include
#define N 110010
char s[N+1];
int main() {
    int i,j,len,max,x,y;
    while(scanf("%s",s)!=EOF){ 
        len=strlen(s);
        for(i=0,max=0;imax){
                    max=2*j+1;
                    x=i-j;
                    y=i+j;
                }
            }
            for(j=0;j<=i&&i+j+1max){
                    max=2*j+2;
                    x=i-j;
                    y=i+j+1;
                }
            }
        }
        printf("%d
",max);
        /*for(i=x;i<=y;i++)
            printf("%c",s[i]);
        printf("
");
        */
    }
    return 0;
}

슬 프 게 도 시간 을 초과 하 다 니!
방법 3: 사고방식 은 여전히 매 거 진 종점 이다. 양쪽 을 보면 얼마나 넓 어 질 수 있 는 지 보지 만 중복 일치 (이하 내용 은 붙 여 넣 기) 를 피한다.
원본 링크:http://www.cnblogs.com/wuyiqi/archive/2012/06/25/2561063.html
알고리즘 의 대략적인 과정 은 이렇다.먼저 두 개의 인접 문자 사이 에 구분자 하 나 를 삽입 합 니 다. 물론 이 구분자 가 원래 문자열 에 나타 나 지 않 아야 합 니 다.일반적으로 '\#' 로 구분 할 수 있다.이렇게 하면 홀수 길이 의 리 턴 문자열 과 짝수 길이 의 리 턴 문자열 을 교묘 하 게 통일 시 켜 고려 한 다음 에 모든 문 자 를 중심 으로 하 는 가장 긴 리 턴 문자열 의 정 보 를 보조 배열 P 로 기록 합 니 다.P [id] 는 문자 str [id] 를 중심 으로 하 는 가장 긴 회 문 열 을 기록 하 는데 str [id] 를 첫 번 째 문자 로 할 때 이 가장 긴 회 문 열 은 오른쪽으로 P [id] 문 자 를 연장 했다.    원본 문자열:    w aa bwsw f d     새 문자열:   # w\# a\# a\# b\# w\# s\# w\# f\# d\# 보조 배열 P:  1 2 1 2 3 2 1 2 1 2 1 4 1 2 1 2 1 2 1     여기 에는 매우 좋 은 성질 이 있 는데 P [id] - 1 은 바로 이 답문 자가 원래 문자열 에 있 는 길이 ('\#' 포함) 이다.만약 이곳 이 특별히 명확 하지 않다 면, 스스로 종 이 를 꺼 내 그림 을 그 려 서 스스로 체득 할 수 있다.물론 여 기 는 모든 사람 이 쓰 는 방법 이 다 를 수 있 지만, 나 는 대체적인 사고방식 이 같 을 것 이 라 고 생각한다.    자, 계속 합 시다.현재 의 관건 은 O (n) 시간 복잡 도 에서 P 배열 을 어떻게 구 하 느 냐 하 는 것 이다.이 P 배열 을 구하 기만 하면 가장 긴 답장 문자열 을 바로 쓸 어 낼 수 있다.    이 알고리즘 은 선형 으로 앞 뒤로 쓸 었 기 때문이다.그러면 우리 가 P [i] 를 구 하려 고 할 때 i 이전의 P [j] 를 우 리 는 이미 얻 었 다.우 리 는 mx 로 i 이전의 답장 문자열 에 기록 하고 가장 오른쪽 끝 까지 뻗 습 니 다.동시에 id 라 는 변수 로 이 최 적 화 된 mx 를 얻 었 을 때의 id 값 을 기록 합 니 다.(주: 문자 비교 시 경 계 를 넘 지 않도록 '\#' 문자열 을 추가 하기 전에 또 다른 특수 문자 '$' 를 추 가 했 습 니 다. 그래서 제 새 문자열 아래 표 시 는 1 부터 시작 합 니 다) 자, 여기까지 코드 를 붙 일 수 있 습 니 다.

void pk()
{
    int i;
    int mx = 0;
    int id;
    for(i=1; i i )
            p[i] = MIN( p[2*id-i], mx-i );        
        else
            p[i] = 1;
        for(; str[i+p[i]] == str[i-p[i]]; p[i]++)
            ;
        if( p[i] + i > mx )
        {
            mx = p[i] + i;
            id = i;
        }
    }
}

    코드 가 짧 지 않 습 니까? 그리고 쓰기 도 아주 좋 습 니 다.편리 하 죠? 제 가 위 에서 말 한 이 알고리즘 은 불필요 한 중복 매 칭 을 많이 피 했 던 것 을 기억 하 시 죠?이것 은 무슨 뜻 입 니까? 사실 이것 이 바로 코드 입 니 다.if( mx > i )     p[i] = MIN( p[2*id-i], mx-i ); 바로 앞에서 비교 한 가장 먼 길이 mx > i 일 때 P [i] 는 가장 작은 값 이 있다.이 알고리즘 의 핵심 사상 은 바로 여기에 있 습 니 다. 왜 P 배열 은 이러한 성질 을 만족 시 킵 니까?
코드 는 다음 과 같 습 니 다:

#include
#define N 110000
char s[2*N+10],str[2*N+10];
int p[2*N+10];

int min(int a,int b) {
    return ai)
                p[i]=min(p[id*2-i],p[id]+id-i);
            else 
                p[i]=1;
                
            for(;str[i+p[i]]==str[i-p[i]];p[i]++);//往两边拓展
            
            if(p[i]+i>max) {
                max=p[i]+i;
                id=i;
            } 
        }
        for(i=0,max=0;imax)
                max=p[i];
        printf("%d
",max-1);
    }
    return 0;
}
/*
waabwswfd
*/