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;
    }
    

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