Boj 2401) 최대 문자열 붙여넣기

KMP

백준 2401

설명

구멍?

요즘은 길이에 점선도 포함시키나? 그거때문에 뻘짓을 좀 했다.

중간에 구멍나도 좋으니 긴 문자열에 짧은 문자열을 최대한 넣어서 채워넣은 총 글자수를 구하는 문제임.

만약 구멍 허용 금지를 하면 아래코드의 if i is not matched 부분만 제거하면 됨.

전략

KMP 로 짧은 문자열이 긴 문자열 어디에 있는지 찾아냄.

그걸 저장해서 DP 를 사용함.

DP 전략은 긴 문자열 맨 뒤에서부터 i 를 두고, i 에서 찾은 짧은 문자열을 p 라고 할 때 모든 p 에 대해서 다음 점화식이 만족됨.

cache[i] = max(cache[i], str_len[p] + cache[i + str_len[p]])

i 에서 i+str_len[p] 까지는 채워넣는게 확정이고 i+str_len[p]~end 는 최댓값을 넣으면 p 에 대해서 최적의 값이기 때문임.

앞에서 말했든 빈칸의 경우 이전의 최댓값을 그대로 들고오면 됨.

그렇게 i=0 까지 반복해서 가장 긴 cache 를 찾아내면 답.

주의할건 메모리가 엄청 부족해서 bitset 으로 어찌어찌 메모리를 줄여야함.

시간 복잡도

긴 문자열 T, 짧은 문자열 중 제일 긴거 P. 짧은 문자열의 갯수 N,

O(len(T)*N + (len(T) + len(P)))

코드

string T;
int32_t failTB[100001];
int32_t n;
bitset<100001> cache_finded[501];
int32_t str_len[501];
int32_t cache[100001];


int main()
{
	fastio;

	cin >> T >> n;
	string str;
	for (int p = 0; p < n; p++)
	{
		cin >> str;
		str_len[p] = str.size();
	
		for (int i = 1, j = 0; i < str.size(); i++)
		{
			while (j > 0 && str[i] != str[j]) j = failTB[j - 1];
			if (str[i] == str[j]) failTB[i] = ++j;
			else failTB[i] = 0;
		}
	
		for (int i = 0, j = 0; i < T.size(); i++)
		{
			while (j > 0 && T[i] != str[j]) j = failTB[j - 1];
			if (T[i] == str[j]) {
				if (str.size() - 1 == j) {
					cache_finded[p].set(i-j, 1);
					cache[i - j] = max(cache[i - j], (int)str.size());
					j = failTB[j];
				}
				else ++j;
			}
		}
	}
	
	int ans = 0;
	for (int i = T.size() - 1; i >= 0; i--)
	{
		for(int p = 0 ; p < n; p++)
			if(cache_finded[p].test(i) && i + str_len[p] < T.size())
					cache[i] = max(cache[i], str_len[p] + cache[i + str_len[p]]);
					
		if(i+1 < T.size())  // if i is not matched
			cache[i] = max(cache[i], cache[i + 1]);
		
		ans = max(ans, cache[i]);
	}
	
	cout << ans;
}