[백준 9253] 스페셜 저지 (C#, C++) - soo:bak

문제 링크

9253번 - 스페셜 저지

설명

두 문자열 A, B와 사용자가 출력한 문자열 S가 주어질 때, S가 두 문자열의 공통 부분 문자열인지 판단하는 문제입니다.

접근법

정답 길이와 동일하다고 가정하므로 S가 A와 B 모두에 포함되면 정답입니다.
KMP로 부분 문자열 포함 여부를 확인합니다.

---

Code

C#

using System;

class Program {
  static int[] BuildLps(string p) {
    var lps = new int[p.Length];
    var len = 0;
    for (var i = 1; i < p.Length; ) {
      if (p[i] == p[len]) lps[i++] = ++len;
      else if (len > 0) len = lps[len - 1];
      else lps[i++] = 0;
    }
    return lps;
  }

  static bool ContainsKmp(string text, string pat) {
    var lps = BuildLps(pat);
    var i = 0;
    var j = 0;
    while (i < text.Length) {
      if (text[i] == pat[j]) {
        i++; j++;
        if (j == pat.Length) return true;
      } else if (j > 0) j = lps[j - 1];
      else i++;
    }
    return false;
  }

  static void Main() {
    var a = Console.ReadLine()!;
    var b = Console.ReadLine()!;
    var s = Console.ReadLine()!;

    var ok = ContainsKmp(a, s) && ContainsKmp(b, s);
    Console.WriteLine(ok ? "YES" : "NO");
  }
}

C++

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;

vi buildLps(const string& p) {
  vi lps(p.size(), 0);
  int len = 0;
  for (int i = 1; i < (int)p.size(); ) {
    if (p[i] == p[len]) lps[i++] = ++len;
    else if (len > 0) len = lps[len - 1];
    else lps[i++] = 0;
  }
  return lps;
}

bool containsKmp(const string& text, const string& pat) {
  vi lps = buildLps(pat);
  int i = 0, j = 0;
  while (i < (int)text.size()) {
    if (text[i] == pat[j]) {
      i++; j++;
      if (j == (int)pat.size()) return true;
    } else if (j > 0) j = lps[j - 1];
    else i++;
  }
  return false;
}

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

  string a, b, s; cin >> a >> b >> s;

  cout << (containsKmp(a, s) && containsKmp(b, s) ? "YES" : "NO") << "\n";

  return 0;
}