BOJ 32927 Longest Common Substring
sorohue가 PS하는 블로그
문제 링크입니다.
문제 요약
최장 공통 부분문자열1이 길이 $K \le 3$의 비트열 $w$이고 길이가 각각 $N$, $M$인 두 비트열 $s$, $t$의 쌍의 개수를 구하세요.
$\vert w \vert \le 3$
두 문자열 $s$와 $t$의 상태를 압축하고자 합니다. 길이가 $w$보다 긴 비트열을 두 문자열이 공통으로 가지면 안 되므로, 두 문자열이 갖는 길이 $K + 1$의 부분문자열 집합 별로 문자열의 개수를 관리할 수 있다면 $s$와 $t$의 공통 부분문자열의 길이가 $K$ 이하이도록 조합하는 것은 두 집합이 공집합인 것만 고르는 것으로 실현할 수 있습니다. 또한 각 문자열이 $w$를 부분문자열로 갖는 조건 역시 $w$를 포함하는 길이 $K+1$의 부분문자열이 집합에 포함되어 있는 지를 확인하는 것으로 해결할 수 있습니다.
마스킹
집합을 관리해야 한다는 점으로부터 문자열을 앞에서부터 채워나가면서 비트 DP를 통해 개수를 세보자는 아이디어가 딸려옵니다.
$K \le 3$이므로 우리는 최대 $2^{K+1} = 16$가지 원소를 갖는 집합을 비트마스킹으로 관리해야 합니다. 따라서 총 $2^{16} = 65536$가지 집합의 상태를 얻습니다.
각 문자열을 생성하면서 어떤 부분문자열을 포함하는 지 확인하기 위해 앞에서부터 문자열을 채워나가면서 길이 $K+1$짜리 접미사를 관리합니다. 맨 앞의 글자를 지우고 다음 글자를 추가하는 방식으로 새로 생기는 부분문자열을 관리할 수 있고, $2^4$의 상태가 곱해집니다.
이제 $d[i][sfx][mask]$를 접미사가 $sfx$고 부분문자열 집합이 $mask$인 길이 $i$의 문자열 개수로 정의해 DP를 통해 길이 $N$의 비트열 중 부분문자열 집합이 $S$인 것의 개수를 카운팅할 수 있습니다. 이 과정의 시간복잡도는 ${\cal O}(N \times 2^{K+1} \times 2^{2^{K+1}})$ 입니다.
실제 구현에서는 토글링 기법으로 메모리 최적화를 해 두었습니다.
조합
WLOG $N \le M$이라고 합시다. $M = K$인 경우 답은 자명하게 1가지입니다.
$N = K < M$인 경우, $s$가 $w$로 고정되므로 $w$를 부분문자열로 갖는 $t$를 찾으면 됩니다. DP로 구한 값 중 $w$를 포함하는 부분문자열이 포함된 집합에 대한 값만 추려서 더하면 됩니다.
$K < N, M$인 경우, $t$를 고정하고 매칭할 수 있는 $s$의 개수를 세는 식으로 접근합니다. $t$의 부분문자열 집합 $T$에 대해, $s$의 부분문자열 집합 $S$는 $T$와의 교집합이 공집합이고 $w$를 포함하는 부분문자열을 원소로 포함해야 합니다.
이를 위해, $w$를 포함하지 않는 부분문자열 집합에 대한 문자열 개수를 전부 0으로 밀어버리면 $U-T$의 부분집합인 모든 $S$에 대한 문자열 개수를 누적 합하는 것으로 원하는 카운팅을 수행할 수 있습니다. 이는 SOS DP로 ${\cal O}(2^{K+1}\times2^{2^{K+1}})$에 전처리할 수 있습니다.
이를 구현하면 총 시간 복잡도 ${\cal O}((N+M) \times 2^{K+1} \times 2^{2^{K+1}})$에 문제를 해결할 수 있습니다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const ll mod = 998244353;
int wmask;
vector<ll> dp(int n, int k){
n -= k+1;
vector<vector<ll>> d(1<<(k+1), vector<ll>(1<<(1<<(k+1)), 0));
vector<vector<ll>> nd(1<<(k+1), vector<ll>(1<<(1<<(k+1)), 0));
for(int i = 0; i < (1<<k+1); i++) d[i][1<<i] = 1;
for(int i = 1; i <= n; i++){
for(int sfx = 0; sfx < (1<<k+1); sfx++){
int nsfx0 = (sfx<<1)&((1<<k+1)-1);
int nsfx1 = (sfx<<1|1)&((1<<k+1)-1);
for(int mask = 0; mask < (1<<(1<<k+1)); mask++){
d[sfx][mask] %= mod;
nd[nsfx0][mask|(1<<nsfx0)] += d[sfx][mask];
nd[nsfx1][mask|(1<<nsfx1)] += d[sfx][mask];
}
}
swap(d, nd); for(int i = 0; i < (1<<k+1); i++) nd[i].clear(), nd[i].resize((1<<(1<<(k+1))));
}
vector<ll> ret(1<<(1<<k+1));
for(int sfx = 0; sfx < (1<<k+1); sfx++) for(int mask = 0; mask < (1<<(1<<k+1)); mask++){
ret[mask] = (ret[mask]+d[sfx][mask]%mod)%mod;
}
return ret;
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int n, m, k; cin >> n >> m >> k;
string w; cin >> w;
if(n > m) swap(n, m);
if(m == k) return !(cout << 1);
int wi = 0; for(auto& i : w) wi = wi<<1|(i-'0');
wmask |= 1<<(wi<<1); wmask |= 1<<(wi<<1|1);
wmask |= 1<<(wi); wmask |= 1<<(wi|(1<<k));
vector<ll> dm = dp(m, k);
if(n == k){
ll ans = 0;
for(int mask = 0; mask < (1<<(1<<k+1)); mask++) if(mask&wmask) ans = (ans+dm[mask])%mod;
return !(cout << ans);
}
vector<ll> dn = dp(n, k);
for(int i = 0; i < (1<<(1<<k+1)); i++) if((i&wmask) == 0) dn[i] = 0;
for(int bit = 0; bit < (1<<k+1); bit++) for(int i = (1<<(1<<k+1))-1; i >= 0; i--){
if(i&(1<<bit)) dn[i] = (dn[i]+dn[i^(1<<bit)])%mod;
}
ll ans = 0;
for(int mmask = 0; mmask < (1<<(1<<k+1)); mmask++){
if((mmask & wmask) == 0 || (mmask & wmask) == wmask) continue;
int nmask = ((1<<(1<<k+1))-1)^mmask;
ans += dm[mmask]*dn[nmask]%mod; ans %= mod;
} cout << ans;
}
어떤 문자열의 부분문자열(substring)은 그 문자열의 맨 앞과 맨 뒤에서 각각 0개 이상의 문자를 지워 얻을 수 있는 문자열입니다. ↩︎