[백준] 21762. 공통 부분 수열 확장

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

접근법

• 공식 해설은 이 곳을 참고하고 나의 접근법을 적어봄
  • https://koi.or.kr/assets/koi/2021/1/solutions/h2-answers.pdf
• 공통 부분 수열이 각각의 문장에서 나타나는 위치를 파악해볼 수 있음
  • 각 문자별 가능한 가장 왼쪽의 위치, 가장 오른쪽의 위치
• 각각의 문장에서 공통 부분 수열의 사이에 들어갈 수 있는 값들이 겹치는 것이 있으면 확장 가능함
  • 가장 왼쪽의 위치 ~ 가장 오른쪽의 위치 사이 문자들을 counting + bitmask 하면서 기록
  • 위치는 지속적으로 증가하므로 슬라이딩 윈도우처럼 사용하면 $O(N)$에 처리 가능함