The problem unexpectedly dosn't contain very tricky tests.
Additionally to forum's examples I add the next:
1. Empty string corresponds with '%%%%%%%%' and so on and
with empty pattern also;
2. 'a'~'%a'
3. String may contain many "like" substrings . For defining
right position dublicable inner '-characters play key role;
4. Dp-method is veru useful, when we are going from ends of strings to their beginnings.

Edited by author 11.07.2007 17:24

My idea is to split the template to multiple templates with no '%', and then search using some modifications of Knuth-Morris-Pratt (except for the first/last template, if there is no '%' at the beginning/end).
I just don't know how fast will it be, because I have not coded it yet...

DP-method is a good idea =)

But I have solution without DP which works for one query as O(max(len1,len2)^2), where len1,len2 - length of string/pattern.

Greedy approach only :)


And in practise this method works more faster then O(max(len1,len2)^2). Look at rating of best solutions (0.001 sec VS 0.921 sec  with DP).

If you want I could tell you about my method.

Edited by author 07.08.2015 20:01