Codeforces 550A. Two Substrings
A問題で簡単だと思って油断すると、怪しいケースを見逃したりするので注意。
問題
長さがnの文字列sが与えられる。
「AB」と「BA」の2つの文字列が部分文字列としてオーバーラップしないように含まれるか？を確認し、含まれるならYES、そうでないならNOを返せ。
1<=n<=10^5
考え方
愚直にABをみつけたらそこをつぶしてからBAを探す方法ではO(n^2)でTLE。
文字列sについて、BAが出現する位置、その個数を求めておく。
すると、ABが出現したとき、BAが他のところで出ていればよく、それは個数をみればよさそうに思う。
しかし、ABAのような場合、ABを見つけたとき、一つ後ろのオーバーラップする位置にあるBAが選べなくなる。なので、個数から1引いて、個数が1以上かどうかを確認する必要がある。
上記以外に、BABのケースの場合、ABをみつけて、一つ前のオーバーラップする位置にあるBAが選べなくなる。なので、同様に個数から1引いて確認すればよい。
その他の場合はオーバーラップしないので、前後に出現するBAを確認し、あれば引いて、そのあとの個数を確認すればよい。
これならO(n)で求められる。
