ABC 452 D - No-Subsequence Substring

D - No-Subsequence Substring

 

시간 제한	메모리 제한
2초	1024MB

문제

(번역)

소문자 알파벳으로 이루어진 문자열 S와 T가 주어집니다.

S의 비어 있지 않은 부분 문자열(substring) s 중에서, T를 (연속적이지 않아도 되는) 부분 수열(subsequence)로 포함하지 않는 것의 개수를 구하세요.

단, S의 두 부분 문자열은 문자열 자체가 같더라도 추출된 위치가 다르면 서로 다른 것으로 간주합니다.

 

입력

• S는 소문자 알파벳으로 구성된 문자열입니다.
• 1 ≤ |S| ≤ 2×10^5
• T는 소문자 알파벳으로 구성된 문자열입니다.
• 1 ≤ |T| ≤ 50

 

출력

정답을 출력하세요.

 

---

풀이

문제 처음 딱 봤을 때 바로 이해하고 "아 DP다!" 하면서 점화식을 쭉 세웠습니다. 완벽한 식이었지만 답은 엄청 크게 나오더라고요. 왜냐면 "부분 문자열 s중에서 T를 부분 수열로 포함하지 않은 것의 개수"를 구하는 문제를 "부분 수열 s중에서 T를 부분 수열로 포함하지 않는 것의 개수"로 이해해버림... 이 사실을 깨달았을 때 남은 시간은 이미 10분이었고 다시 생각해본 결과 점화식을 세우기까지는 못했지만 어떻게 풀어야 하는지는 생각이 났습니다. 너무 아쉽지만 정리된 생각으로 대회 끝나고 AC를 받았기 때문에 풀이를 정리해서 올려봅니다.

 

먼저 S의 길이가 20만이기 때문에 O(N^2)으로는 풀 수 없습니다. 최소 O(NM)은 생각해봐야 합니다. 여기서 DP 문제라는 힌트를 얻을 수 있었습니다.

 

S의 i번째 문자 Si를 확인했을 때, 이걸로 지금까지 확인해본 모든 부분 문자열을 체크해볼 수 있을까요? 진짜 모든 부분 문자열을 확인한다면 O(N^2)이 되기 때문에 안됩니다. 여기서 확인해봐야 할 것은 T가 완성되지 않은 부분 문자열입니다.

 

S의 i번째 문자 Si까지를 부분 문자열로 구성하는 모든 경우를 계속 살펴보면 어떨까요? Si까지로 만들어지는 조건에 맞는 모든 경우의 수를 계속 확인하며 다음 문자인 Si+1, Si+2, ...를 붙여가며 경우의 수를 확인합니다.

i-1번째 문자를 끝으로 하는 부분 문자열은 현재 9개가 남아있습니다. 그리고 지금까지의 모든 경우의 수는 res로 관리되고 있다고 해봅시다. 이제 i번째 문자를 현재 존재하는 모든 문자열에 붙여보겠습니다. (이 문자열의 집합은 실제로 하나하나 관리되지 않습니다.)

두 개의 문자가 빨간색이 되었습니다. 이 문자는 i번째 문자를 붙임으로 인해 T를 부분 수열로 구성할 수 있게 된 부분 문자열입니다. 이 부분 문자열들은 조건에 맞지 않기 때문에 이제 경우의 수에서 제거해줍니다. 그리고 i번째 문자 하나만으로 구성되는 새로운 경우가 추가되었습니다. 이제 집합에 존재하는 부분 문자열의 수는 8개가 되었습니다. i번째 문자를 끝으로 하며 조건에 맞는 부분 문자열의 수 8을 res에 더해줍니다. 이 과정을 S의 끝 문자까지 반복하면 res에는 결국 S의 모든 각 문자를 끝으로 하는 부분 문자열 중, T를 부분 수열로 갖지 않는 경우가 모두 들어있게 됩니다.

 

이제 조건에 맞는 부분 문자열들을 어떻게 관리할 것인지가 문제입니다. 이 문자열들은 진짜 문자열 정보를 담을 필요 없이 T의 몇 번째 글자까지 부분 수열로 구성할 수 있는지만 알면 됩니다. T의 길이가 L이라고 했을 때, L에 도달한 문자들은 제거해주면 됩니다.

 

dp 배열을 다음과 같이 정의해봅니다.

dp_i[j] = S의 i번째 문자를 끝으로 하면서 T의 j번째 글자까지 부분 수열로 만들 수 있는 부분 문자의 수

dp_i라고 넘버링을 붙이니까 dp배열을 2차원으로 구성해야 할 것 같은 느낌이지만 그렇지 않습니다. dp_i는 dp_i-1의 정보만을 필요로 하기 때문에 하나의 배열로 관리가 가능합니다.

 

dp_i[j]의 점화식을 이렇게 세워볼 수 있겠습니다.

j = 0일 때, S[i] != T[0]이라면 dp_i[j] += 1
j = 1일 때, S[i] == T[j]라면, dp_i[0] = 0
S[i] == T[j]일 때, dp_i[j] = dp_i-1[j-1]
S[i] != T[j+1], dp_i[j] = dp_i-1[j]

뭐가 되게 복잡한데, 그냥 Si가 T의 문자에 포함되는지 살펴보면 됩니다. 즉, T의 길이만큼을 S의 각 문자마다 순회하면 됩니다. O(NM)으로 해결할 수 있게 되었습니다.

 

중요한 건 이 부분입니다. Si가 T[j]와 같다면, j-1번째 문자를 끝으로 한 dp_i-1[j-1]의 모든 경우의 수는 dp_i[j]로 옮겨집니다. 그리고 Si가 T[j+1]과 같다면, dp_i-1[j]의 모든 경우의 수는 다음으로 옮겨지기 때문에 비어버립니다. 만약 T[j] == T[j+1]인 경우는 무엇을 먼저 처리해야 할까요? 후자를 먼저 처리해야 합니다. 그래야 데이터 오염이 없습니다. 즉, S의 모든 문자를 순차적으로 확인하되, T의 문자는 역순으로 확인해야 합니다. 

 

정답 코드

S = input().strip()
T = ' '+input().strip()
L = len(t)-1

dp = [0] * L
res = 0

for i in S:
    for j in range(L-1,0,-1):
        if i == T[j+1]:
            dp[j] = 0
        if i == T[j]:
            dp[j] += dp[j-1]
        if j == 1 and i == T[1]:
            dp[j] += 1
        res += dp[j]
    if i == T[1]:
        dp[0] = 0
    else:
        dp[0] += 1
    res += dp[0]

print(res)