SRM409 Div2 500

とぷこだ 過去問

問題

文字列配列wordsの超文字列Xとは、

  • wordsの各要素がXの部分文字列
  • x_1<=...<=x_nとなるようなインデックス列が存在する(nはwordsの要素数)。x_kはwords[k]がXに出現する場所。

たとえば、"abca"は{"abc","ca"}の超文字列。x_1=0,x_2=2とすることができる。
文字列配列が与えられる時、最短の超文字列の長さを返す。

考え方

インデックスx_kは順番にでなくてはいけないので、文字列words[i]のx_iがx_(i-1)以上になるように文字列を追加していけば超文字列を作れる。
(i-1)番目までを使った超文字列にwords[i]を加えるとすると、x_(i-1)以降にwords[i]があれば、インデックスはそのまま。途中まであれば、残りを追加してインデックスはそのまま。もし見つからなければ、超文字列の最後に追加してインデックスは追加する前の超文字列の最後にする。