PALINDROMIZE 문제에서 계속 오답이 뜹니다...

  • slywind
    slywind

    알고리즘 문제 해결전략에 있는 코드와 거의 차이가 없어보이는 코드인데 계속 오답이 뜹니다...

    KMP알고리즘을 사용해 pi를 찾은 후 maxOverlap을 찾습니다.

    다만 책과 차이라면 속도를 높이려고 벡터가아닌 포인터를 사용했다는것과, 문자열을 뒤집지 않고 뒤에부터 읽은 것 뿐입니다..

    계속 안되서 다시 C++스타일로(벡터랑 string)으로 코딩하니 이번에는 성공했습니다.

    아래 코드에서 무엇이 문제일까요..

    #include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX_LEN 100002

using namespace std;

int maxOverlap(char *str, int len) {

    // init

    int *pi = new int[MAX_LEN]();

    // make pi

    int begin = 1, matched = 0;
    while (begin + matched < len) {

        if (str[begin + matched] == str[matched]) {
            matched++;
            pi[begin + matched - 1] = matched;
        }
        else {
            if (matched == 0) begin++;
            else {
                begin += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }

    // find
    begin = 0; matched = 0;
    while (begin < len) {

        if (matched < len && str[begin + matched] == str[len - 1 - matched]) {
            matched++;
            if (begin + matched == len) {
                delete[] pi;
                return matched;
            }
        }
        else {

            if (matched == 0)
                begin++;
            else {
                begin += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }

        }

    }

    delete[] pi;

    return 0;
}

/* main */

int main() {

    int c;
    cin >> c;
    getchar();

    while (c-- > 0) {

        char *str = new char[MAX_LEN]();
        int len, ret;

        fgets(str, MAX_LEN, stdin);
        len = strlen(str);
        if (str[len - 1] == '\n') {
            str[strlen(str) - 1] = '\0';
            len--;
        }

        ret = maxOverlap(str, len);
        printf("%d\n", len + len - ret);

        delete[] str;
    }


    return 0;
}

    6년 전
0개의 댓글이 있습니다.

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.