I was thinking about a substring matching, but if that's not what you need,
then you still have the same number of strings, but finding a matching in a
string would take quadratic time on the length of the string, instead of
linear time.
2010/5/20 vignesh radhakrishnan
> @Marcio, I get your algo
@Mario Your estimate of no. of strings, I guess doesn't consider strings of
length less than length H or W.
it would order(4H^2+4W^2) approximately.
I guess I 've understood it right. correct me if I'm wrong
On 20 May 2010 07:23, Mario Ynocente Castro wrote:
> I don't think 1014 needs any speci
I think you have to look at this book "Algorithms on Strings, Trees and
Sequences: Computer Science and Computational Biology"
By Dan gusfield. It has wonderful data structure which works really fast for
string operations.
On Wed, May 19, 2010 at 4:16 PM, vignesh radhakrishnan <
rvignesh1...@g
@Marcio, I get your algo now. So a substring match is also a match. I get
your approach. Thank you.
Any ideas for the second problem?
On 20 May 2010 10:45, vignesh radhakrishnan wrote:
> @Mario Your estimate of no. of strings, I guess doesn't consider strings of
> length less than length H or W
Use trie data structure ,construct it from given matrix
On Thu, May 20, 2010 at 7:23 AM, Mario Ynocente Castro wrote:
> I don't think 1014 needs any special algorithm, if we've got an H x W
> matrix, then we've got (4H+4W-2) strings in which you must look, and you can
> do this with a greedy stra
I don't think 1014 needs any special algorithm, if we've got an H x W
matrix, then we've got (4H+4W-2) strings in which you must look, and you can
do this with a greedy strategy.
2010/5/19 vignesh radhakrishnan
> I'm trying to solve some string problems somewat efficiently. Can someone
> tell me
I'm trying to solve some string problems somewat efficiently. Can someone
tell me what would be efficient DS for solving these problems
http://acm.jlu.edu.cn/joj/showproblem.php?pid=1014
http://acm.jlu.edu.cn/joj/showproblem.php?pid=1873
Thanks,
Regards,
Vignesh
--
There are two kinds of people.
