[G3] 백준 1701번 Cubeditor C++ KMP, 문자열, 브루트포스 알고리즘

리뷰

 

브루트포스 알고리즘을 통해 문자열의 길이를 줄이며 각 문자열의 LPS를 구하는 문제

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

 

전역 변수

• str : 탐색을 진행할 문자열 변수
• n, ans : 초기 문자열의 길이 n, 가장 긴 길이를 저장할 변수 ans

 

함수

1. getLPS

void getLPS(string str)

 

문자열의 LPS를 구하는 함수

1. 매개 변수는 초기 문자열에서 왼쪽의 문자열이 한개씩 날아간 문자열들이 주어진다.
2. 해당 문자열에서의 LPS를 구하고 LPS중 가장 큰 값이 ans에 저장되게 된다.

 

문제풀이

1. 초기 문자열 str을 입력 받고 n에 str의 길이를 저장한다.
2. n번의 for문을 개행하고 str의 왼쪽에서부터 한글자씩 제거하며 getLPS함수의 매개변수로 전달해 준다.
3. n번의 반복문을 끝내고 ans에 저장된 답을 출력해 준다.

 

참고 사항

• n번의 for문을 통해 왼쪽에서부터 문자를 제거하는 이유는 탐색 인덱스를 항상 0번으로 하면 안되기 때문이다.
• 그냥 LPS를 구해도 예제는 정답이 잘 출력 되므로 나처럼 혼동하지 않아야 한다.

 

정답 코드

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

using namespace std;
string str;
int n, ans;

void getLPS(string str) {
	int cur = 0, i = 1, length = str.size();
	vector<int> lps(n, 0);
	while (i < length) {
		if (str[cur] == str[i]) {
			cur++;
			lps[i] = cur;
			ans = max(ans, cur);
			i++;
		}
		else {
			if (cur != 0) cur = lps[cur - 1];
			else {
				lps[i] = 0;
				i++;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	getline(cin, str);

	n = str.size();
	for (int i = 0; i < n; i++) getLPS(string(str.begin() + i, str.end()));

	cout << ans << "\n";
}