[백준] 1701 Cubeditor

May 25, 2021 ( last updated : May 25, 2021 )
KMP 알고리즘

https://github.com/sneakstarberry/

Abstract

[백준] 1701번 Cubeditor

[백준] 1701번 Cubeditor

백준 1701번

알고리즘 유형

풀이방법

KMP 알고리즘을 이용해서 풀어야한다. KMP를 통해서 match된 글자 중에 수가 가장 긴 글자 수를 쉽게 구할 수 있다.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

string S;

vector<int> getPartialMatch(string &N) {
  int M = N.size();
  vector<int> pi(M, 0);
  int begin = 1, matched = 0;

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

  return pi;
}

int main() {
  cin >> S;
  int result = 0;
  for (int i = 0; i < S.size(); i++) {
    string temp = S.substr(i, S.size());

    vector<int> pi = getPartialMatch(temp);

    sort(pi.begin(), pi.end(), greater<int>());
    result = max(result, pi[0]);
  }

  cout << result << endl;
  return 0;
}

Originally published May 25, 2021
Latest update May 25, 2021

Related posts :

{# #}