Codeforces Beta Round #71 C

こどふぉす 過去問

問題

文字列strが与えられる。さらに、いくつか文字列boring[i]が与えられる。
文字列strの部分文字列の中で、boring[i]が含まれない最長の文字列の長さとその最初の文字の場所を答える。

考え方

しゃくとりっぽくやる。部分文字列の最初の位置begと最後+1の位置endを更新していく。
もし、部分文字列[beg,end)にboringが含まれないならば、end++で更新。
もし、部分文字列[beg,end)にboringが含まれるならば、begをboringが含まれない位置まで更新。


部分文字列[beg,end)は、end++で更新するので、もしboringが含まれるとしたら、部分文字列の最後の部分でboringな文字列が見つかる。なので、「boringが含まれるかどうか」は部分文字列の最後の部分だけを比較すればいい。
begの更新は、見つかったboringの長さ-1の場所ならば含まれなくなるので、新しいbegは「end-(boring[i].length()-1)」の場所にする。


BABBABBAB, boring->ABBの場合は、

[BA]BBABBAB
[BAB]BABBAB
[BABB]ABBAB <-boringが見つかった！3文字なのでend-2の位置にbegを移動。
BA[BB]ABBAB
BA[BBA]BBAB
...