1701번: Cubeditor
Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 ��
www.acmicpc.net
입력으로 주어지는 문자열 H와 H의 모든 부분문자열 N에 대해 KMP-search 를 수행하여 H에 N과 일치하는 문자열이 2개 이상 존재하는 N 중에서 길이가 가장 긴 부분문자열의 길이를 출력해주면 된다.
다만, 부분문자열 N의 길이를 1에서부터 시작하면 시간이 너무 오래걸리므로, 이분탐색을 활용하여 시간복잡도를 줄였다. (그래도 오래 걸리는건 함정;;)
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<int> getPartialMatch(string& N) {
int Nlen = N.length();
vector<int> pi(Nlen, 0);
int begin = 1, matched = 0;
while (begin + matched < Nlen) {
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;
}
bool KMP_search(string& H, string& N) {
int Hlen = H.length(), Nlen = N.length();
vector<int> pi = getPartialMatch(N);
int cnt = 0;
int begin = 0, matched = 0;
while (begin <= Hlen - Nlen) {
if (matched < Nlen && H[begin + matched] == N[matched]) {
matched++;
if (matched == Nlen) {
cnt++;
if (cnt == 2) return true;
}
}
else {
if (matched == 0)
begin++;
else {
begin += matched - pi[matched - 1];
matched = pi[matched - 1];
}
}
}
return false;
}
int allPartialStrSearch(string str) {
int ret = 0;
int len = str.length();
int start = 1, end = len;
while (start <= end) {
int mid = (start + end) / 2;
if (mid == 0) break;
for (int i = 0; i + mid <= len; i++) {
string N = str.substr(i, mid);
if (KMP_search(str, N)) {
ret = mid;
start = mid + 1;
break;
}
}
if (start != mid + 1)
end = mid - 1;
}
return ret;
}
int main(void) {
string str;
cin >> str;
cout << allPartialStrSearch(str) << endl;
return 0;
}
알고리즘 200일 프로젝트 - 165 day
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 2573번: 빙산 (0) | 2020.09.21 |
|---|---|
| 백준 11404번: 플로이드 (0) | 2020.09.20 |
| 백준 16236번: 아기 상어 (0) | 2020.09.20 |
| 백준 1389번: 케빈 베이컨의 6단계 법칙 (0) | 2020.09.20 |
| 백준 1707번: 이분 그래프 (0) | 2020.09.20 |
