[c++] 백준 1701 - Cubeditor(KMP알고리즘)

0. [c++] 백준  -

https://www.acmicpc.net/problem/1701

1. 풀이

1) 처음 코드는 모든 위치에서의 부분 문자열을 만들어서 비교를 통해서 반복되는 문자열 중 최대 길이를 구해내는 방식의 구현을 만들었었다.

 이 코드의 구현은 N^2의 구현으로 입력이 5000자리 이하의 입력이여서 손쉽게 통과할 줄 알았지만....

이 구현에서 최악의 경우가 존재하는데, 모든 입력이 aaaaaaaaaaaaaa...와 같은 형태일 경우이다.

이런 경우에 문자열을 매칭하는 부분에서 자리수에 비례하는 연산을 반복하게 되는데, 이런 경우 5000*5000*5000의 반복을 통해 시간 제한을 초과하게 되버렸다.

2) 이제 이러한 문제를 해결하기 위해서 KMP알고리즘을 활용하였다.(https://kyunstudio.tistory.com/138)

이전에 KMP알고리즘을 하며 짚더미를 만드는 알고리즘이 있었는데, 자기 자신을 탐색하면서 실패한 경우 matched의 크기에 맞게 그 지점부터 탐색을 하게 만드는 pi[]배열이 있었다.

이 배열을 활용하여 문제를 해결해 보았다.

우선 KMP알고리즘에서 pi[k]배열에 담기는 수는 k지점에서의 matched의 크기를 담는다.

이렇게 설명하니 이해하기 힘들 수 있을것 같은데...

abcabc라는 배열이 있다 가정하자.

pi[0](a) = 0

pi[1](ab) = 0

pi[2](abc) = 0

pi[3](abc'a') = 1

pi[4](abc'ab') = 2

pi[5](abc'abc') = 3

이런 식으로 진행이 된다.

이때, 이 문제에서 가장 중요한 부분은, 반복되는 문자열이 존재하면, 그 크기의 최대값을 구하는 것이다.

그래서 그 최대값을 구하는 형태의 함수로 살짝 손봐서 문제를 해결하였다.

KMP알고리즘을 활용하니 시간 제한을 만족시키며 문제를 해결 할 수 있었다.

2. 소스코드

1)(시간 초과)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

#include<iostream> #include<vector> #include<algorithm> #include<string>   using namespace std;   int commonPrefix(const string& input, int i, int j) {     int k = 0;      while (i < input.size() && j < input.size() && input[i] == input[j]) {         i++; j++; k++;     }     return k; }   int main() {       ios_base::sync_with_stdio(0);         cin.tie(0);     string input;     cin >> input;     int ret = 0;     for (int i = 0; i < input.size(); i++)         for (int j = i + 1; j < input.size(); j++)             ret = max(ret, commonPrefix(input, i, j));              cout << ret;     return 0;   } Colored by Color Scripter

cs

2) KMP알고리즘을 활용한 풀이

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

#include<iostream> #include<vector> #include<algorithm> #include<string>   using namespace std;   int commonPrefix(const string& input, int i, int j) {     int k = 0;      while (i < input.size() && j < input.size() && input[i] == input[j]) {         i++; j++; k++;     }     return k; }   int KMP(const string& input) {     int m = input.size();     vector<int> pi(m, 0);     int ret = 0;     int begin = 1, matched = 0;     while (begin + matched < m) {         if (input[begin + matched] == input[matched]) {             matched++;             pi[begin + matched - 1] = matched;             ret = max(ret, matched);         }         else {             if (matched == 0)                 ++begin;             else {                 begin += matched - pi[matched - 1];                 matched = pi[matched - 1];             }         }       }     return ret; }   int main() {       ios_base::sync_with_stdio(0);         cin.tie(0);     string input;     cin >> input;     int ret = 0;     /*for (int i = 0; i < input.size(); i++)         for (int j = i + ret + 1; j < input.size(); j++)             ret = max(ret, commonPrefix(input, i, j));*/       for (int i = 0; i < input.size(); i++) {         string cutFront = input.substr(i, input.size());         ret = max(ret, KMP(cutFront));     }              cout << ret << endl;     return 0;   } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!