Infinite String

$T$에 한 번이라도 등장하는 문자들의 집합을 $C$라고 하자.

먼저, 공통 부분수열에 포함되는 모든 문자는 $T^\infty$에 등장해야 하므로 반드시 $C$에 속해야 한다. 따라서 답은 $S$에서 $C$에 속하는 문자의 개수를 넘을 수 없다.

반대로, $S$에서 $C$에 속하는 문자만 순서대로 모두 골라 만든 문자열을 $X$라고 하자. $X$의 각 문자는 $T$의 어딘가에 등장한다. 현재까지 $T^\infty$의 어느 위치까지 사용했더라도, 그 뒤의 다음 개 문자 안에는 원하는 문자가 다시 등장한다. 그러므로 의 문자를 앞에서부터 차례대로 모두 고를 수 있고, 는 의 부분수열이다.

따라서 답은 $S$의 문자 중 $T$에 한 번이라도 등장하는 문자의 개수이다. $T$에 등장하는 문자를 표시한 뒤 $S$를 한 번 순회하면 된다.

시간 복잡도는 $O(|S|+|T|)$이고, 추가 공간 복잡도는 $O(1)$이다.

Solution written by GPT5.6