글 읽기 - 잘못된 부분 좀 찾아주세요ㅠ(c++)

112224 4년 전 0

초기 인덱스를 한칸씩 뒤로 밀면서 문자열에 대한 실패함수를 작성했습니다.( abbdaab ->bbdaab->bdaab->....)

틀린 부분이 잘 안보여요 ㅠ

작성하다가 똑같은 아이디어로 substr을 이용했더니 맞았습니다.

1번 코드에서 잘못된 부분 좀 알려주시면 감사하겠습니다.

////////WA//////////


#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
using namespace std;

const int si = 5010;
string t;
int ans = 0;
void setPi()
{
	int len = t.length();
	for (int k = 1; k < len; k++)    //밀어낼 인덱스의 갯수-1
	{
		vector<int>pi(len + 1,0);
		int j = 0;    //접두사 인덱스
		for (int i = k; i < len; i++)    //접미사 인덱스
		{
			while (j > 0 && t[j+k-1] != t[i])    //k-1 만큼 뒤로
				j = pi[j - 1];
			if (t[j+k-1] == t[i])
			{
				pi[i] = ++j;
				ans = max(ans, pi[i]);
			}
		}
		/*for (int i = 0; i < t.length(); i++)
			cout << pi[i] << ' ';
		cout << "\n\n";*/
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	getline(cin, t);
	setPi();
	cout << ans << '\n';
}







////////AC//////
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
using namespace std;

const int si = 5010;
string t;
int ans = 0;
void setPi()
{

	int len2 = t.length();
	for (int k = 0; k < len2; k++)
	{
		string tmp = t.substr(k);
		int len = tmp.length();
		vector<int>pi(len + 1, 0);
		int j = 0;
		for (int i = 1; i < len; i++)
		{
			while (j > 0 && tmp[j] != tmp[i])
				j = pi[j - 1];
			if (tmp[j] == tmp[i])
			{
				pi[i] = ++j;
				ans = max(ans, pi[i]);
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	getline(cin, t);
	setPi();
	cout << ans << '\n';
}

112224 4년 전 0

18~35 부분에서 k의 시작값이 문제인 것 같아 다음과 같이 바꿔봤으나, 도중에 WA 판정이 나옵니다 ㅠㅠ

반례나 틀린 부분 알려주시면 감사하겠습니다.

    for (int k = 0; k < len; k++)    //밀어낼 인덱스의 갯수-1
	{
		vector<int>pi(len + 1,0);
		int j = 0;    //접두사 인덱스
		for (int i = k+1; i < len; i++)    //접미사 인덱스
		{
			while (j > 0 && t[j+k] != t[i])    //k-1 만큼 뒤로
				j = pi[j - 1];
			if (t[j+k] == t[i])
			{
				pi[i] = ++j;
				ans = max(ans, pi[i]);
			}
		}
	}

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

문제

문제

출처

ICPC

잘못된 부분 좀 찾아주세요ㅠ(c++)

112224 4년 전 0

112224 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말