[백준 16916] 부분 문자열 (C#, C++) - soo:bak

문제 링크

16916번 - 부분 문자열

설명

문자열 S 안에 패턴 P가 연속 부분 문자열로 존재하는지 판정하는 문제입니다.

접근법

문자열 길이가 최대 100만이므로 단순히 모든 위치에서 비교하면 시간 초과가 발생합니다. KMP 알고리듬을 사용하면 선형 시간에 판정할 수 있습니다.

먼저 패턴의 실패 함수를 계산합니다. 실패 함수는 각 위치에서 접두사와 접미사가 일치하는 최대 길이를 저장합니다. 이 정보를 이용하면 불일치가 발생했을 때 처음부터 다시 비교하지 않고 적절한 위치로 건너뛸 수 있습니다.

이후, 텍스트를 순회하며 패턴과 비교합니다. 일치하면 다음 문자로 진행하고, 불일치하면 실패 함수를 참조해 패턴의 비교 위치를 조정합니다. 패턴 끝까지 일치하면 1을 출력하고, 텍스트 끝까지 찾지 못하면 0을 출력합니다.

Code

C#

using System;

namespace Solution {
  class Program {
    static int[] BuildPi(string p) {
      var m = p.Length;
      var pi = new int[m];
      var j = 0;
      for (var 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;
    }

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

    static void Main(string[] args) {
      var s = Console.ReadLine()!;
      var p = Console.ReadLine()!;
      Console.WriteLine(KMP(s, p));
    }
  }
}

C++

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

typedef vector<int> vi;

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

  string s, p;
  cin >> s >> p;
  int n = s.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;
  }

  for (int i = 0, j = 0; i < n; i++) {
    while (j > 0 && s[i] != p[j])
      j = pi[j - 1];
    if (s[i] == p[j]) {
      if (j == m - 1) {
        cout << 1 << "\n";
        return 0;
      }
      j++;
    }
  }
  cout << 0 << "\n";

  return 0;
}