Re: [algogeeks] String Problems
Use trie data structure ,construct it from given matrix On Thu, May 20, 2010 at 7:23 AM, Mario Ynocente Castro ycma...@gmail.comwrote: 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 rvignesh1...@gmail.com 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. Those who care for others and The others -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mario Ynocente Castro Undergraduate Student of System Engineering National University of Engineering, Peru http://sites.google.com/site/ycmario -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] String Problems
@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 rvignesh1...@gmail.com wrote: @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 ycma...@gmail.com 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 strategy. 2010/5/19 vignesh radhakrishnan rvignesh1...@gmail.com 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. Those who care for others and The others -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mario Ynocente Castro Undergraduate Student of System Engineering National University of Engineering, Peru http://sites.google.com/site/ycmario -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- There are two kinds of people. Those who care for others and The others -- There are two kinds of people. Those who care for others and The others -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] String Problems
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...@gmail.com wrote: 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. Those who care for others and The others -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -- If u doubt your believes,u believe ur doubts If u fail to practise,u practises failure Thanks and Regards GopiNath -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] String Problems
@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 ycma...@gmail.com 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 strategy. 2010/5/19 vignesh radhakrishnan rvignesh1...@gmail.com 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. Those who care for others and The others -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mario Ynocente Castro Undergraduate Student of System Engineering National University of Engineering, Peru http://sites.google.com/site/ycmario -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- There are two kinds of people. Those who care for others and The others -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] String Problems
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 rvignesh1...@gmail.com @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 rvignesh1...@gmail.comwrote: @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 ycma...@gmail.com 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 strategy. 2010/5/19 vignesh radhakrishnan rvignesh1...@gmail.com 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. Those who care for others and The others -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mario Ynocente Castro Undergraduate Student of System Engineering National University of Engineering, Peru http://sites.google.com/site/ycmario -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- There are two kinds of people. Those who care for others and The others -- There are two kinds of people. Those who care for others and The others -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mario Ynocente Castro Undergraduate Student of System Engineering National University of Engineering, Peru http://sites.google.com/site/ycmario -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] String Problems
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. Those who care for others and The others -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] String Problems
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 rvignesh1...@gmail.com 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. Those who care for others and The others -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mario Ynocente Castro Undergraduate Student of System Engineering National University of Engineering, Peru http://sites.google.com/site/ycmario -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
