ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1177. Like Comparisons

1177- Good problem
Posted by svr 11 Jul 2007 17:23
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
Re: 1177- Good problem
Posted by Dexter 7 Apr 2010 19:39
svr wrote 11 July 2007 17:23
Dp-method is veru useful, when we are going from ends of strings to their beginnings.

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...
Re: 1177- Good problem
Posted by LLI_E_P_JI_O_K 7 Aug 2015 20:01
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