글 읽기 - 문자열 주기 예측문제 질문드립니다.

kkw564 6년 전 0

실패함수를 구해서 결국 최대가 되는 것들만 더해주는 과정을 반복했는데

어느 부분에서 반례가 잡히는지 잘 모르겠습니다.

지적해주시면 정말 감사하겠습니다.

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

using namespace std;

typedef long long ll;

string s, p;

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;
}

int main()
{
	int n;
	cin >> n;
	
	string str;
	cin >> str;

	vector<int> vc = getPi(str);

	ll ans = 0;
	int pos = 0;
	for (int i = 0; i < vc.size(); i++)
	{
		if (vc[i] == 0)
			continue;

		else if (vc[i])
		{
			if (str[0] == str[i])
			{
				pos = i;
				ans += i;
			}

			else
			{
				ans += pos;
			}
		}
	//	cout << " i :: " << i << " ans :: " << ans << endl;
	}
	cout << ans;
	return 0;
}

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

문제

문제

출처

ICPC

문자열 주기 예측문제 질문드립니다.

kkw564 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말