글 읽기 - kmp로 풀었는데 반례가 뭘까요..

balance0591 3년 전 0

게시판에 있는 반례는 다 넣어봐서 다 맞았어요 어디가 문제일까요 KMP로 풀었습니다.

#include <iostream>
#include <cstring>

using namespace std;


char arr[1100000];
char pattern[1100000];
char pi[1100000];
int cnt = 0;

void kmp(char* pat) {
    int n = strlen(pat);
    int i = -1, j = 0;
    pi[j] = i;
    while (j < n) {
        if (i == -1 || (i >= 0 && pat[i] == pat[j])) {
            i++;
            j++;
            pi[j] = i;
        }
        else i = pi[i];
    }
}

//문자열 비교
void find_pattern(char* arr, char* pat) {
    int n = strlen(arr);
    int m = strlen(pat);
    int i = 0, j = 0;
    while (i < n) {
        if (j == -1 || (j >= 0 && arr[i] == pat[j])) i++, j++;
        else if (arr[i] != pat[j]) j = pi[j];
        if (j == m) {
            cnt++;
            j = pi[j];
        }
    }
}
int main() {
    int n, m;
	cin >> n >> m >> arr;

    pattern[0] = 'I';
    for (int i = 1; i <= 2*n; i+=2) {
     
        pattern[i] = 'O';
        pattern[i+1] = 'I';
    }
    kmp(pattern);
    find_pattern(arr, pattern);
	cout << cnt;
    return 0;
}

kth001 3년 전 0

pi가 char라서 n값이 커지면 오버플로가 나서 값이 음수가 됩니다 pi를 int로 바꾸니 맞았습니다 뜨네요

balance0591 3년 전 0

하....하.. 드디어 해결됐네요...정말 감사합니다.

공부를 더해야겠습니다 ㅜㅜ

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

문제

문제

출처

ICPC

kmp로 풀었는데 반례가 뭘까요..

balance0591 3년 전 0

kth001 3년 전 0

balance0591 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말