パナソニックプログラミングコンテスト2020 E. Three Substrings
問題
3つの文字列a,b,cが与えられる。
これらの文字列は、以下の方法で作られたことがわかっている。
- ある文字列sがあり、その連続部分文字列tを取り出す
- tのいくつかの文字を'?'に置き換える
このとき、元の文字列sの長さとして考えられる最小の長さを求めよ。
制約
- 1 <= |a|, |b|, |c| <= 2000
- a,b,cは英小文字または'?'からなる文字列
解法
aとbの合体した文字列に、cがマッチするか？をチェックすると、全体でO(|a| * |c| * |c|)かかってしまって間に合わない。
そこで、文字列aを固定して、文字列bと文字列cがあり得る位置を全探索することを考える。
すると、文字列bと文字列cがあるiとjの位置におけるかどうか？のチェックはO(1)かO(logN)程度で行わなければいけない。
文字列aに対して、文字列bがある位置iにおけるかどうか？は、前計算でO(|a|*|b)で求めておける。
具体的には、文字列aの前後に十分な長さの'?'からなる文字列を付け加えたものを考えれば良い。
同様に、文字列aに対して、文字列cがある位置jにおけるかどうかも、前計算しておける。
したがって、文字列bと文字列cがi,jにおけるかはO(1)で判断できる。
しかし、これでは不十分で、文字列bと文字列cの相対的な位置関係がvalidかどうかも必要になる。
ただ、これも同様に文字列bに対して文字列cの相対的な位置k(負もありえる)がおけるかも前計算できるので、O(1)で判断できる。
よって、文字列bと文字列cの位置を全探索すれば、その時の元の文字列sの長さが求められるので、それの最小値を返せばよい。全体でO(N^2)程度。
