【AtCoder ABC452D】
部分列を含まない部分文字列
（Common Lisp）

• AtCoder ABC452DはSの部分文字列のうちTを部分列として含まないものを数える問題です。
• 左端を固定したとき「Tを含む最短部分文字列の右端」がわかれば、それ以降は含むと一括判定できます。
• nxtテーブルで次に文字が現れる位置を前計算しておくことで、右端を高速に求めて正解できます。

1. 問題

英小文字からなる文字列 $S, T$ が与えられます。

$S$ の空でない部分文字列 $s$ のうち、
$T$ を（連続するとは限らない）部分列として含まないものの個数を求めてください。

ここで、$S$ の 2 つの部分文字列は、取り出した箇所が異なれば文字列として等しくても区別するものとします。

• 文字列 $X$ の部分文字列とは、
  $X$ の先頭から $0$ 文字以上、末尾から $0$ 文字以上を削除して得られる文字列のことを指します。
• 文字列 $X$ の部分列とは、
  $X$ の要素を $0$ 個以上選んで削除し、残った要素を元の順序を保って並べた文字列のことを指します。

制約

• $S$ は英小文字からなる文字列
• $|S|$ を $S$ の長さとして、$1 \le |S| \le 2 \times 10^5$
• $T$ は英小文字からなる文字列
• $|T|$ を $T$ の長さとして、$1 \le |T| \le 50$

入力

入力は以下の形式で標準入力から与えられる。

S
T

出力

答えを出力せよ。

D – No-Subsequence Substring

1.1. 例

abrakadabra
aba

出力

51

2. 素朴な回答(6)

まずは、素朴な回答として、substrpでは、tsの文字がその順番で s に出てくることを調べました。

;; O(N)
(defun substrp (s ts)
  (let* ((idx 0))
    (loop for ch across s 
	  while (< idx (length ts))
	  do (when (equal (aref ts idx) ch) (incf idx)))
    (= idx (length ts))))Code language: Lisp (lisp)

それを、すべての部分文字列を作ってチェックしました。

;; O(N^4)
(defun count-not-subsequence-substr (s ts)
  (declare (type string s ts))
  (loop for i from 0 below (length s)
	sum (loop for j from (1+ i) to (length s)
		  count (not (substrp (subseq s i j) ts)))))Code language: Lisp (lisp)

Sの部分文字列の生成が２重のループになっていて、しかもsubseqで文字列生成をしていて、検査でもループを回しているので、全体でO(N^4)になっています。

結果は、正解 6、時間切れ 50。

(defun solve()
  (let* ((s (read-line))
	 (ts (read-line)))
    (princ (count-not-subsequence-substr s ts))))

;; O(N^4)
(defun count-not-subsequence-substr (s ts)
  (declare (type string s ts))
  (loop for i from 0 below (length s)
	sum (loop for j from (1+ i) to (length s)
		  count (not (substrp (subseq s i j) ts)))))

;; O(N)
(defun substrp (s ts)
  (let* ((idx 0))
    (loop for ch across s 
	  while (< idx (length ts))
	  do (when (equal (aref ts idx) ch) (incf idx)))
    (= idx (length ts))))
#-swank
(solve)Code language: Lisp (lisp)

2.1. ある部分文字列を含む部分文字列

すべての部分文字列を検査する、というやり方では、時間内に回答を得られなさそうです。
どうにかして、グループ化して同じ検査を省略する必要があります。

部分列を「含む」部分文字列を書き出してみると、最小の文字列から拡張した文字列は、すべて含むことになります。

* (print-subsequence-substr s ts)

"abra" 
"abrak" 
"abraka" 
"abrakad" 
"abrakada" 
"abrakadab" 
"abrakadabr" 
"abrakadabra" ; ここまでは "abra-"を含む

"brakadabra"  ; これは "akadabra"を含む
"rakadabra" 
"akadabra" 
"kadabra"     ; これは、"adabra"を含む
"adabra"      ; これは、"abdra"を含む
"dabra" 
"abra" 

* (print-min-substrs s ts)
"abra" 
"akadabra" 
"adabra" 
"abra" Code language: Lisp (lisp)

この判定では、ある部分文字列S_iで部分列Tを含む時、S_iを拡張した部分文字列S_i+1も含む、という事実を使えていません。

3. 部分文字列の終端から数える

そこで、左端 left を固定したときに、部分文字列の終端を位置 right をなんとか求められた（search-subseq-right）、とします。
そうすれば、 length – right + 1 が「含む」部分文字列の数になります。

(defun count-subsequence-by-left (left s ts nexts)
  (declare (type fixnum left)
	   (type string s ts)
	   (type (vector * *)))
  (max (- (1+ (length s))
	  (search-subseq-right left s ts nexts))
       0))Code language: Lisp (lisp)

あとは、leftを 0〜length まで動かしていって合計すれば「含む」部分文字列の数を求められます。
あとは、Sで作成できる部分文字列の総数 length * (length+1) / 2 から引けば、「含まない」部分文字列を求められます。

(defun all-subseq-patterns (s)
  (declare (type string s))
  (/ (* (length s) (1+ (length s))) 2))

(defun count-not-subsequence-substr/nexts (s ts)
  (declare (type string s ts))
  (let* ((nexts (make-nexts s ts)))
    (- (all-subseq-patterns s)
       (loop for i from 0 below (length s)
	     sum (count-subsequence-by-left i s ts nexts)))))
Code language: Lisp (lisp)

3.1. 次に文字 ch が出てくる位置を記録する

では、どうやって部分文字列の終端位置を求めるか、です。
これは「次に文字 ch が出てくる位置」を記録しておく方法があります。

$l$ を固定したときの $r_{\max}(l)$ の求め方を考えます。

これは、次の関数

$$\operatorname{nxt}(i, c) = \text{「}S\text{ において } i \text{ 文字目以降で文字 } c \text{ が初めて現れる位置」}$$

を、すべての $i, c$ について前計算しておけば、部分列 DP（subsequence DP, 文字列の部分列を扱う動的計画法）の要領で求められます。

解説 – AtCoder Beginner Contest 452

そこで、Tで出てくる文字について、次にいつ出てくるのか、という表を用意しました。

(defun make-charset (str)
  (declare (type string str))
  (sort (remove-duplicates str)
	(lambda (a b)
	  (< (char-code a) (char-code b)))))

(defun char-num (ch)
  (declare (type character ch))
  (- (char-code ch) (char-code #\a)))

;; nxs[idx ch] => next pos whose char is ch
(defun make-nexts (s ts)
  (declare (type string s ts))
  (let* ((charset (make-charset ts))
	 (nexts-vec
	   (make-array 26
		       :element-type 'fixnum
		       :initial-element most-positive-fixnum))
	 (result
	   (make-array (list (length s) 26)
		       :element-type 'fixnum
		       :initial-element most-positive-fixnum )))
    (loop for idx from (1- (length s)) downto 0 do
      (loop for ch across charset do
	(setf (aref result idx (char-num ch))
	      (aref nexts-vec (char-num ch)))
	(when (equal ch (aref s idx))
	  (setf (aref nexts-vec (char-num ch)) idx)))
	  finally (return result))))
Code language: Lisp (lisp)

make-nextsは、二次元配列 nexts[s][26] を返します。
ここに、indexとchar-numを入れれば、次に文字までワープできます。
これを順繰りにすれば、すぐにTを「含む」部分文字列の終端までたどり着けます。

;; returns end pos of subsequence.
(defun search-subseq-right (left s ts nexts)
  (declare (type fixnum left)
	   (type string s ts)
	   (type (vector * *)))
  (loop with idx = left
	while (< idx (length s))
	for j from (if (equal (aref s idx) (aref ts 0))
		       1 0)
	  below (length ts)
	do (setf idx (aref nexts idx
			   (char-num (aref ts j))))
	finally (return (1+ idx))))
Code language: Lisp (lisp)

3.2. 正解 56

無事に正解 56。

(defun solve()
  (let* ((s (read-line))
	 (ts (read-line)))
    (princ (count-not-subsequence-substr/nexts s ts))))

(defun make-charset (str)
  (declare (type string str))
  (sort (remove-duplicates str)
	(lambda (a b)
	  (< (char-code a) (char-code b)))))

(defun char-num (ch)
  (declare (type character ch))
  (- (char-code ch) (char-code #\a)))

;; nxs[idx ch] => next pos whose char is ch
(defun make-nexts (s ts)
  (declare (type string s ts))
  (let* ((charset (make-charset ts))
	 (nexts-vec
	   (make-array 26
		       :element-type 'fixnum
		       :initial-element most-positive-fixnum))
	 (result
	   (make-array (list (length s) 26)
		       :element-type 'fixnum
		       :initial-element most-positive-fixnum )))
    (loop for idx from (1- (length s)) downto 0 do
      (loop for ch across charset do
	(setf (aref result idx (char-num ch))
	      (aref nexts-vec (char-num ch)))
	(when (equal ch (aref s idx))
	  (setf (aref nexts-vec (char-num ch)) idx)))
	  finally (return result))))

;; returns end pos of subsequence.
(defun search-subseq-right (left s ts nexts)
  (declare (type fixnum left)
	   (type string s ts)
	   (type (vector * *)))
  (loop with idx = left
	while (< idx (length s))
	for j from (if (equal (aref s idx) (aref ts 0))
		       1 0)
	  below (length ts)
	do (setf idx (aref nexts idx
			   (char-num (aref ts j))))
	finally (return (1+ idx))))

(defun count-subsequence-by-left (left s ts nexts)
  (declare (type fixnum left)
	   (type string s ts)
	   (type (vector * *)))
  (max (- (1+ (length s))
	  (search-subseq-right left s ts nexts))
       0))

(defun all-subseq-patterns (s)
  (declare (type string s))
  (/ (* (length s) (1+ (length s))) 2))

(defun count-not-subsequence-substr/nexts (s ts)
  (declare (type string s ts))
  (let* ((nexts (make-nexts s ts)))
    (- (all-subseq-patterns s)
       (loop for i from 0 below (length s)
	     sum (count-subsequence-by-left i s ts nexts)))))
  
#-swank
(solve)Code language: Lisp (lisp)