I solve this task during contest with greedy+hash. My solution take O(n) time, but i'm interest how i can solve this without hash?

use z-algorithm

You can use prefix function from KMP algorithm.

Simple KMP on suffixes will TLE on good tests, cause u will need to run it n times.
This problem has very weak tests.

My first idea was to use naive suffix finding algorithm for short suffix and only if there is no short (with length about 500) common suffixes then run KMP and find long one.
However I managed to get AC only with naive suffix finding algo.

Why n times? Jury solution calculates prefix-function only one time.

Can you explain your solution via KMP prefix func? Thanks!

+1
i wrote it, but have tl..

I solved it using z-algorithm.

Edited by author 23.03.2009 17:26

How to solve it with one kmp:
a) find kmp(s1+"#"+s2)
b) if there is 0 kmp-value at any position in s2, "Yes"
c) use the fact that you can stop every prefix at any time, i.e. abrab, b is 'bad' letter, so you can output abr and continue with prefix ab