언제나 처음처럼

[문제 링크]

입력으로 주어지는 문자열 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