Codeforces ラウンド #272 (ディビジョン 1)C(String DP)_html/css_WEB-ITnose

C. Dreamoon と Strings

テストごとの制限時間

1 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

Dreamoonには文字列 s とパターン文字列 p。彼はまず、結果として得られた文字列から正確に x 文字を削除します。次に、s 内で見つかる p に等しい重複しない部分文字列の最大数として定義される計算を行います。彼はこの数値をできるだけ大きくしたいと考えています。

より正式には、s から正確に x 文字を削除することで取得できる、すべての s の最大値として定義しましょう。 Dreamoon は、0 から |s| までのすべての x について知りたいと考えています。 ここで|s| 文字列 s の長さを示します。

入力

入力の最初の行には、文字列 s (1?≤?|s|?≤?2?000) が含まれます。

入力の 2 行目には、 string p (1?≤?|p|?≤?500).

どちらの文字列も小文字の英字のみで構成されます。

出力

Print |s|?+?1 スペースで区切られた整数を a 0 から |s| までのすべての x を表す単一の線。

入力

aaaaaaa

入力

rrリー

出力

リー

题意：RT

思路：dp[i][j] 表示の前i个字符一共適合了j个p串、删掉の最少字数

先用一个一数en [i]预预预处理处理在在的的每位置位置i min (dp[ en[i+1] ][j+1] ，dp[ i ][j] + (en[i+1]-i-m) )