글 읽기 - kmp 문제 모르겠습니다..

ruz 4년 전 0

s[k]부터 시작하는 모든 부분문자열에 대해 kmp 돌리는 식으로 풀려고했는데

잘 안되네요..

접근을 잘못한걸까요?

#include<cstdio>

int n, pi[5001], ans;
char s[5001];
int max(int a, int b) { return a > b ? a : b; }
int main() {
	scanf("%s", s);
    // k=비교시작위치
	for (int k = 0; s[k]; ++k) {
		pi[k] = k;
		for (int i = k + 1, j = k; s[i]; ++i) {
			while (j > k && s[i] != s[j])
				j = pi[j - 1];
			if (s[i] == s[j])
                //pi[k]=k 로 저장했으므로 pi[i]-k이 매칭길이가 됩니다.
				ans = max(ans, (pi[i] = ++j) - k);
		}
	}
	printf("%d", ans);
}

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

문제

문제

출처

ICPC

kmp 문제 모르겠습니다..

ruz 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말