[Baekjoon] 2401번 최대 문자열 붙여넣기(C++)

www.acmicpc.net/problem/2401

2401번: 최대 문자열 붙여넣기

 

Level: Level 2

풀이: 기존 풀이 참고

Language: C++

 

 

문제설명

어떤 긴 문자열이 주어지고 여러 개의 짧은 문자열들이 주어질 때 이때 짧은 문자열을 긴 문자열에 붙여 넣을 때 가장 길게 붙여 넣는 경우를 찾아라. 단 이때 짧은 문자열들끼리는 교차할 수 없다. (‘aabbc'에 'aab'와 'bbc' 둘 다 붙여 넣는 것은 불가능하다.) 또, 짧은 문자열은 여러 번 사용할 수 있다.

 

 

입력/출력

입력

첫 번째 줄에는 가장 긴 문자열이 주어지고 두 번째 줄에는 짧은 문자열의 숫자 N(1 ≤ N ≤ 500)이 입력으로 주어진다. 세 번째 줄부터 N개의 줄에는 짧은 문자열이 주어진다.

가장 긴 문자열의 길이 L은 (1 ≤ L ≤ 100,000) 짧은 문자열의 길이 l은 (1 ≤ l ≤ 10,000)이다.

입력 예

aabcc

2

aab

bcc

 

출력

붙여 넣은 짧은 문자열들의 길이의 총합을 출력한다.

출력 예

3

 

 

풀이

문제는 이해했으나 어떻게 해결하는지에 대해 고민해보다가 결국 다른 사람들의 풀이를 보고 그곳에서 사용하는 알고리즘과 해결한 코드를 보고 이해하는 걸로 결정하였다.

짧은 문자열들을 긴 문자열의 각 위치마다 일일이 매칭을 시도해보는 방법을 제안하였다. 긴 문자열 H에서 짧은 문자열 S가 시작할 수 있는 위치를 찾는데 한 개가 아닌 N개의 문자열에 대해서 생각해야 한다. 최적화할 수 있는 방법으로 긴 문자열에서 짧은 문자열을 찾는 알고리즘인 KMP를 제안하였다.

KMP Algorithm

•  정의: 어떤 문자열 H와 S가 주어졌고 H가 S보다 긴 경우에, H 안에 S가 포함되어 있는지를 탐색하는 알고리즘, 인덱스 1만 옮기지 말고, 일치하는 부분은 옮겨도 된다고 말한다. 이미 얻은 정보를 활용하여 문자열 S를 빠르게 옮기는 것이다.

•  S에서 0번째 인덱스를 제외한 다른 인덱스들에 대해 접두사와 접미사가 일치하는 부분을 알아야 한다는 것이다.

•  시간 복잡도: O(N+M), H의 길이를 N, S의 길이를 M

실패 함수

• 실패 함수를 F(k)라고 하면, 0번째 인덱스를 제외한 각 인덱스에서 해당 인덱스까지의 부분 문자열 중 접두사와 접미사가 일치하는 최대 길이로 k가 인덱스일 경우 F(k)라고 한다.

• 각 인덱스에서 접두사==접미사인 부분

 

Code

#include <iostream>
#include <bitset>
#include <algorithm> //max
using namespace std;

//KMP 알고리즘 이용
string L; //긴 문자열
string W; //짧은 문자열
//메모리를 더 줄이기 위해서 bitset을 사용
bitset<100005> can_use[505];
int N; //짧은 문자열의 숫자
int l; //긴 문자열의 길이
int fail[10001], len[10001], cache[100001];

int solve(int idx) {
	if (idx == l) return 0;
	int& ret = cache[idx];
	if (ret != -1) return ret;
	ret = solve(idx + 1);
	for (int i = 0; i < N; ++i) {
		if (can_use[i][idx]) ret = max(ret, len[i] + solve(idx + len[i]));
	}
	return ret;
}

int main() {
	//속도 향상
	cin.tie(NULL); 
	cout.tie(NULL); 
	ios::sync_with_stdio(false);

	memset(cache, -1, sizeof(cache));
	cin >> L >> N;
	l = L.size(); //긴 문자열의 길이

	for (int k = 0; k < N; ++k) {
		cin >> W; //짧은 문자열
		memset(fail, 0, sizeof(fail));

		int w = W.size();
		len[k] = w;

		for (int i = 1, j = 0; i < w; ++i) {
			while (j && W[i] != W[j]) 
				j = fail[j - 1];
			if (W[i] == W[j]) 
				fail[i] = ++j;
		}

		for (int i = 0, j = 0; i < l; ++i) {
			while (j && L[i] != W[j]) 
				j = fail[j - 1];
			if (L[i] == W[j]) {
				if (j == w - 1) {
					can_use[k][i - j] = true;
					j = fail[j];
				}
				else ++j;
			}
		}
	}
	cout << solve(0);
	return 0;
}

 

 

ScreenShot

 

참고

문제: https://devbelly.tistory.com/27

문제: https://mapocodingpark.blogspot.com/2020/05/BOJ-2401.html

KMP 알고리즘: https://baeharam.github.io/posts/algorithm/kmp/