글 읽기 - 최대 문자열을 붙여넣고 싶습니다.. 도와주세요

kkw564 6년 전 0

kmp와 dp를 이용하여 문제를 풀어나가려 했습니다.

dp를 다음과 같이 설정했습니다.

dp[i] :: i번째 일때 최대 문자열을 붙인 길이

for (int i = 0; i < vc.size(); i++)
{
int start = vc[i].first.first;
int end = vc[i].first.second;
int size = vc[i].second;

dp[end + 1] = max(dp[end + 1], dp[end - size + 1] + size);
}

이렇게 구성하며 dp를 구성해나갔는데 반례를 못찾겠습니다.

제가 문자열을 잘 붙여나갈 수 있도록 도와주실 분을 구합니다.. 도와주세요..

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

typedef pair<int, int> pii;

string s, p[502];
int dp[100004];

vector<pair<pii, int > > vc;
map<string, int> mp;

vector<int> getPi(string p)
{
	int m = (int)p.size();
	int j = 0;

	vector<int> pi(m, 0);

	for (int i = 1; i< m; i++) {
		while (j > 0 && p[i] != p[j])
			j = pi[j - 1];
		if (p[i] == p[j])
			pi[i] = ++j;
	}
	return pi;
}
vector<int> kmp(string s, string p)
{
	vector<int> ans;
	auto pi = getPi(p);
	int n = (int)s.size(), m = (int)p.size(), j = 0;
	for (int i = 0; i < n; i++) {
		while (j>0 && s[i] != p[j])
			j = pi[j - 1];
		if (s[i] == p[j]) {
			if (j == m - 1) {
				ans.push_back(i - m + 1);
				j = pi[j];
			}
			else {
				j++;
			}
		}
	}
	return ans;
}

int main()
{
	cin >> s;

	int n;
	cin >> n;

	int idx = 0;
	for (int i = 0; i < n; i++)
	{
		string t;
		cin >> t;

		if (!mp.count(t))
		{
			mp[t] = 1;
			p[idx] = t;
			idx++;
		}
	}

	for (int i = 0; i < idx; i++)
	{
		vector<int> ans = kmp(s, p[i]);
		int len = ans.size();
		for (int j = 0; j < len; j++)
		{
			int start = ans[j];
			int end = ans[j] + p[i].size() - 1;
			int size = p[i].size();
			vc.push_back({ {start,end},size });
		}
	}

	sort(vc.begin(), vc.end());

	for (int i = 0; i < vc.size(); i++)
	{
		int start = vc[i].first.first;
		int end = vc[i].first.second;
		int size = vc[i].second;

		dp[end + 1] = max(dp[end + 1], dp[end - size + 1] + size);
	}

	int cnt = 0;
	for (int i = 0; i <= s.size() + 2; i++)
		cnt = max(cnt, dp[i]);
	
	cout << cnt;

	return 0;
}

smu201111192 6년 전 2

반례입니다.

aabbbbbbbbaa

kkw564 6년 전 0

문제 이해를 잘못했네요 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

최대 문자열을 붙여넣고 싶습니다.. 도와주세요

kkw564 6년 전 0

smu201111192 6년 전 2

kkw564 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말