BOJ 5582: 공통 부분 문자열

작성일

https://www.acmicpc.net/problem/5582

  • 2월동안 187문제 풀기(지난달 누적 87개) (30/187)
  • 난이도 적힌거에 비해 너무 쉬워서 눈을 의심했건만.. Suffix Array 문제였다.
  • SA를 쓰면 엄청 빠르게 풀린다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;

string a, b;
int dp[4001][4001], ans;

int main() {
  cin >> a >> b;

  for(int i = 0; i < a.size(); i++)
    for(int j = 0; j < b.size(); j++)
      if(a[i] == b[j]) {
        dp[i+1][j+1] = dp[i][j] + 1;
        ans = max(ans, dp[i+1][j+1]);
      }
  cout << ans;
}