글 읽기 - 40% 쯤에서 틀립니다 문제가 뭔지 도저히 모르겠어요...

qlqnf16 3년 전 1

게시판에 있는 반례들 모두 돌려봐도 제대로 나옵니다

뭐가 문제일까요..?

#include <cstdio>
#include <iostream>
#include <string>
#define MAX 1000000 + 5
using namespace std;

string text;
string pattern;
char k[MAX];
int ans[MAX];
int TL, PL, ansIdx;

void getK() {
  int j = 0;
  for (int i = 1; i < PL; i++) {
    while (j > 0 && pattern[i] != pattern[j])
      j = k[j - 1];
    if (pattern[i] == pattern[j])
      k[i] = ++j;
  }
}

void kmp() {
  int j = 0;
  for (int i = 0; i < TL; i++) {
    while (j > 0 && text[i] != pattern[j]) {
      j = k[j - 1];
    }
    if (text[i] == pattern[j]) {
      if (j == PL - 1) {
        ans[ansIdx++] = i - j + 1;
        j = k[j];
      } else {
        j++;
      }
    }
  }
}

void solve() {
  PL = pattern.size();
  TL = text.size();
  getK();
  kmp();

  printf("%d\n", ansIdx);
  for (int i = 0; i < ansIdx; i++) {
    printf("%d ", ans[i]);
  }
}

int main() {
  getline(cin, text);
  getline(cin, pattern);
  solve();
  return 0;
}

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

문제

문제

출처

ICPC

40% 쯤에서 틀립니다 문제가 뭔지 도저히 모르겠어요...

qlqnf16 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말