[백준 1786] 찾기 (C#, C++) - soo:bak

문제 링크

1786번 - 찾기

설명

텍스트 T에서 패턴 P가 등장하는 모든 시작 위치를 찾는 문제입니다. 길이가 최대 100만이고 공백도 포함될 수 있습니다.

접근법

단순히 모든 위치에서 패턴을 비교하면 O(nm) 시간이 걸려 시간 초과가 발생합니다. KMP 알고리듬을 사용하면 O(n+m)에 해결할 수 있습니다.

KMP의 핵심 아이디어는 매칭이 실패했을 때 이미 비교한 정보를 버리지 않는 것입니다. 예를 들어 ABCDABD 패턴을 ABCDAB까지 일치시켰다가 7번째 문자에서 실패하면, 앞의 AB와 뒤의 AB가 같다는 것을 이미 알고 있습니다. 따라서 처음부터 다시 비교하지 않고 3번째 문자부터 비교를 이어갈 수 있습니다.

이를 위해 부분 일치 테이블을 미리 계산합니다. 이 테이블은 패턴의 각 위치에서 접두사와 접미사가 일치하는 최대 길이를 저장합니다. ABCDABD의 경우 6번째 위치까지의 부분 문자열 ABCDAB에서 접두사 AB와 접미사 AB가 일치하므로 테이블 값은 2입니다.

이후, 텍스트를 순회하며 패턴과 비교합니다. 일치하면 다음 문자로 진행하고, 불일치하면 부분 일치 테이블을 참조해 패턴의 비교 위치를 조정합니다. 패턴 끝까지 일치하면 현재 위치를 기록하고, 다음 매칭을 찾기 위해 테이블을 참조해 비교를 계속합니다.

모든 매칭 위치를 찾은 후 개수와 위치 목록을 출력합니다.

Code

C#

using System;
using System.Collections.Generic;

namespace Solution {
  class Program {
    static int[] BuildPi(string p) {
      var m = p.Length;
      var pi = new int[m];
      for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && p[i] != p[j])
          j = pi[j - 1];
        if (p[i] == p[j])
          pi[i] = ++j;
      }
      return pi;
    }

    static void Main(string[] args) {
      var text = Console.ReadLine()!;
      var pat = Console.ReadLine()!;
      var n = text.Length;
      var m = pat.Length;

      var pi = BuildPi(pat);
      var pos = new List<int>();

      for (int i = 0, j = 0; i < n; i++) {
        while (j > 0 && text[i] != pat[j])
          j = pi[j - 1];
        if (text[i] == pat[j]) {
          if (j == m - 1) {
            pos.Add(i - m + 2);
            j = pi[j];
          } else j++;
        }
      }

      Console.WriteLine(pos.Count);
      if (pos.Count > 0)
        Console.WriteLine(string.Join(" ", pos));
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  string T, P;
  getline(cin, T);
  getline(cin, P);
  int n = T.size();
  int m = P.size();

  vi pi(m, 0);
  for (int i = 1, j = 0; i < m; i++) {
    while (j > 0 && P[i] != P[j])
      j = pi[j - 1];
    if (P[i] == P[j])
      pi[i] = ++j;
  }

  vi ans;
  for (int i = 0, j = 0; i < n; i++) {
    while (j > 0 && T[i] != P[j])
      j = pi[j - 1];
    if (T[i] == P[j]) {
      if (j == m - 1) {
        ans.push_back(i - m + 2);
        j = pi[j];
      } else j++;
    }
  }

  cout << ans.size() << "\n";
  for (int i = 0; i < (int)ans.size(); i++)
    cout << ans[i] << (i + 1 == (int)ans.size() ? '\n' : ' ');

  return 0;
}