Timeline for Longest common substring in linear time
Current License: CC BY-SA 3.0
66 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 1, 2022 at 14:42 | history | edited | caird coinheringaahing ♦ |
edited tags
|
|
| Apr 9, 2021 at 15:06 | history | protected | caird coinheringaahing ♦ | ||
| Apr 9, 2021 at 15:06 | history | unprotected | caird coinheringaahing ♦ | ||
| Aug 2, 2019 at 19:43 | history | protected | Community Bot | ||
| Jul 7, 2017 at 13:33 | history | unprotected | Community Bot | ||
| May 23, 2017 at 12:41 | history | edited | Community Bot |
replaced http://stackoverflow.com/ with https://stackoverflow.com/
|
|
| S May 15, 2017 at 14:42 | history | bounty ended | jimmy23013 | ||
| S May 15, 2017 at 14:42 | history | notice removed | jimmy23013 | ||
| S May 7, 2017 at 20:13 | history | bounty started | jimmy23013 | ||
| S May 7, 2017 at 20:13 | history | notice added | jimmy23013 | Draw attention | |
| Apr 13, 2017 at 12:48 | history | edited | Community Bot |
replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/
|
|
| Mar 28, 2017 at 20:25 | comment | added | Magic Octopus Urn |
Isn't this always worst case O(nlog(n))? I mean, judging by the amount of attention obviously not, but can someone explain to me why? I've read the full wiki page on suffix trees and it only solidified my confusion on the worst case performance of suffix trees being O(n)...
|
|
| Feb 7, 2017 at 2:50 | comment | added | user62131 | @FlipTack: Agreed. I've protected it because it's attracting people who think "I can solve that" without reading the question, and my experience is that such questions tend end up needing protection eventually (additionally, the protection banner is, here, a clue that the question has obvious wrong answers). | |
| Feb 7, 2017 at 2:47 | history | protected | Community Bot | ||
| S Feb 5, 2017 at 10:15 | history | bounty ended | izzyg | ||
| S Feb 5, 2017 at 10:15 | history | notice removed | izzyg | ||
| Feb 1, 2017 at 6:54 | history | unprotected | Community Bot | ||
| S Feb 1, 2017 at 6:36 | history | bounty started | izzyg | ||
| S Feb 1, 2017 at 6:36 | history | notice added | izzyg | Reward existing answer | |
| Jan 26, 2017 at 20:35 | comment | added | FlipTack | This must be the question with the most deleted answers per valid answer... | |
| Jan 25, 2017 at 21:42 | history | edited | xnor | CC BY-SA 3.0 |
So that answerers don't miss the complexity requirement.
|
| Jan 25, 2017 at 16:33 | history | edited | mbomb007 | CC BY-SA 3.0 |
added 46 characters in body
|
| Jan 25, 2017 at 4:02 | answer | added | Mitch Schwartz | timeline score: 44 | |
| Jan 4, 2017 at 22:28 | comment | added | user9206 | @Gareth [a-z] is ok. | |
| Jan 4, 2017 at 21:17 | comment | added | Gareth |
What alphabet will the input strings be drawn from? [a-z]? [a-zA-Z]? [a-zA-Z0-9]?
|
|
| Jul 22, 2016 at 9:38 | comment | added | Syamesh K | Done a simple program for the answer, but its O(N^2). | |
| Jul 13, 2016 at 15:01 | comment | added | user9206 | @mbomb007 It's a good idea. Not sure how to supply the test input though. | |
| Jul 11, 2016 at 18:37 | comment | added | mbomb007 | @Lembik You should just make the question [fastest-code], where the program with the best worst-case in big-oh notation wins. Then you'll at least get some answers, and in the even that someone can solve it in O(n), they'll win. | |
| Jul 8, 2016 at 19:18 | comment | added | applejacks01 | I'm not smart enough to write an O(n), but I did like the idea so wrote up a working solution. var a = "xxxappleyyyyyyy"; var b = "zapplezzz"; (a,b)=>{ var len = Math.min(b.length,a.length); while(len > 0){ for(var i1 = 0; i1 < a.length - len; i1++){ for(var i2 = 0; i2 < b.length - len; i2++){ var str1 = a.substring(i1,i1+len); var str2 = b.substring(i2,i2+len); if(str1 === str2){ return {Index1: i1+1, Index2: i1 + len, String: str1}; } } } len-- } } | |
| May 8, 2016 at 15:10 | history | bumped | Community Bot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Feb 23, 2016 at 22:27 | history | edited | Conor O'Brien |
edited tags
|
|
| Jun 18, 2015 at 5:06 | comment | added | mellamokb | I have just about completed a C# implementation (not golfed) that implements the suffix tree. Still working out all the little bugs, which are fairly difficult to track down... I'm still not quite grasping how to convert the suffix tree code into a code that finds longest common substring. | |
| Jun 16, 2015 at 18:37 | history | edited | user9206 | CC BY-SA 3.0 |
added 63 characters in body
|
| Jun 16, 2015 at 18:34 | comment | added | user9206 | @Agawa001 I am not sure 100% sure what you mean. Say you have two strings of length 10^6 each. What is the longest your idea could possibly take? | |
| Jun 14, 2015 at 19:39 | comment | added | user9206 | @mellamokb Oh yes... Gusfield is a world expert but apparently not at drawing figures! | |
| Jun 14, 2015 at 0:25 | comment | added | mellamokb |
The first example file seems to have a lot of mistakes. It's difficult to separate my misinterpretation of the algorithm from the mistakes in the document... For example, Figure 6.1 has 3 misplaced $. Figure 6.2 has two extra $ and incorrect labelling of the top edge. Figure 6.4 is missing the final b on edge 2... and that's all the farther I've gotten so far.
|
|
| Jun 13, 2015 at 21:22 | history | protected | Community Bot | ||
| Jun 13, 2015 at 20:40 | history | edited | user9206 | CC BY-SA 3.0 |
added 2 characters in body
|
| May 19, 2015 at 20:07 | comment | added | Martin Ender | @Azee See Lembik's reply (you may not have got a notification because your answer was converted to a comment.) | |
| May 19, 2015 at 19:15 | comment | added | user9206 | Java is fine. I have a standard ubuntu set up with 8GB of RAM. | |
| May 19, 2015 at 19:13 | comment | added | Azee | I'm pretty close to a Java solution that works without any of the suffix tree brain surgery. I have been running tests simple strings and sentences. The time complexity of the solution is bounded well below O(n^2) but space complexity is high due to String objects and data structures required. I need to know these details before posting the solution: 1. Are you open to a Java solution? 2. If so, what is your machine config and JVM heap size? | |
| S Mar 13, 2015 at 12:06 | history | bounty ended | Community Bot | ||
| S Mar 13, 2015 at 12:06 | history | notice removed | Community Bot | ||
| Mar 12, 2015 at 6:30 | history | edited | user9206 | CC BY-SA 3.0 |
added 24 characters in body
|
| Mar 12, 2015 at 6:27 | comment | added | user9206 | @KSFT The suffix tree ones or the suffix array ones? I can try to help if there is a particular point you are stuck on. | |
| Mar 11, 2015 at 23:06 | comment | added | KSFT | Wow...I cannot understand any of those explanations. | |
| Mar 7, 2015 at 9:55 | comment | added | user9206 | @KSFT This part sets out the time and space complexity .... "In fact, the reduction in the number of nodes is such that the time and space requirements for constructing a suffix tree are reduced from O(N2) to O(N). " | |
| Mar 6, 2015 at 21:46 | comment | added | KSFT | The article at the second link you provide under "Useful information" says that "constructing [a suffix tree] requires O(N^2) time" | |
| Mar 5, 2015 at 19:37 | comment | added | user9206 | @mbomb007 Surely not for 007 :) Would you be happy with n log n instead? I have tried to add lots of detail for the algorithms but can add more if that would help. | |
| Mar 5, 2015 at 19:35 | comment | added | mbomb007 |
Still, O(n) is pretty discouraging.
|
|
| Mar 5, 2015 at 19:28 | comment | added | user9206 | @mbomb007 I wasn't planning on testing with huge strings! I just meant the strings will be substrings of the huge strings I linked to. This was to provide example input to be helpful. | |
| Mar 5, 2015 at 19:26 | comment | added | mbomb007 |
Not worth attempting. If you weren't worried about O(n) and planning to use huge strings to test, maybe then it would.
|
|
| S Mar 5, 2015 at 10:17 | history | bounty started | Community Bot | ||
| S Mar 5, 2015 at 10:17 | history | notice added | user9206 | Draw attention | |
| Mar 3, 2015 at 13:17 | history | edited | user9206 | CC BY-SA 3.0 |
added 117 characters in body
|
| Mar 3, 2015 at 13:08 | history | edited | user9206 | CC BY-SA 3.0 |
added 216 characters in body
|
| Mar 3, 2015 at 12:55 | history | edited | user9206 | CC BY-SA 3.0 |
added 17 characters in body
|
| Mar 3, 2015 at 12:53 | comment | added | user9206 | @FUZxxl I have updated the question with links to clear explanations with examples and useful source code. I hope that helps! | |
| Mar 3, 2015 at 12:48 | history | edited | user9206 | CC BY-SA 3.0 |
added 732 characters in body
|
| Mar 3, 2015 at 12:10 | comment | added | FUZxxl | @Lembik Sorry, but these are very complex algorithms and it's not really fun to golve 100+ lines of code. | |
| Mar 2, 2015 at 17:55 | history | tweeted | twitter.com/#!/StackCodeGolf/status/572455198335094784 | ||
| Mar 2, 2015 at 16:47 | history | edited | user9206 | CC BY-SA 3.0 |
added 63 characters in body
|
| Mar 2, 2015 at 16:28 | history | edited | Martin Ender |
edited tags
|
|
| Mar 2, 2015 at 16:13 | comment | added | user9206 | @Capture_A_Lag Yes! I know you can do it via a suffix tree or suffix array and maybe other ways too. | |
| Mar 2, 2015 at 16:12 | comment | added | Oleksii Savenkov |
O(n) time Are you sure it is possible?
|
|
| Mar 2, 2015 at 16:04 | history | asked | user9206 | CC BY-SA 3.0 |