PALINDROMIZE 문제에서 계속 오답이 뜹니다... 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일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
slywind
알고리즘 문제 해결전략에 있는 코드와 거의 차이가 없어보이는 코드인데 계속 오답이 뜹니다...
KMP알고리즘을 사용해 pi를 찾은 후 maxOverlap을 찾습니다.
다만 책과 차이라면 속도를 높이려고 벡터가아닌 포인터를 사용했다는것과, 문자열을 뒤집지 않고 뒤에부터 읽은 것 뿐입니다..
계속 안되서 다시 C++스타일로(벡터랑 string)으로 코딩하니 이번에는 성공했습니다.
아래 코드에서 무엇이 문제일까요..
7년 전