Timeline for Finding all-but-one matches
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 3, 2015 at 16:13 | history | edited | ror3d | CC BY-SA 3.0 |
added 1229 characters in body
|
| Mar 2, 2015 at 15:47 | comment | added | ror3d | Yes, but a lot more memory than it would be manageable, the naive approach. I'll look for something that could simplify it. | |
| Mar 2, 2015 at 15:26 | comment | added | user9206 | Was the faster method dynamic programming? That could take O(n^2) time. | |
| Mar 2, 2015 at 14:17 | comment | added | ror3d | Maybe, but for 15K I found a longest match of only 40 characters, so it is a very small improvement. Thank you anyway, I'll take it into account when trying a new version. | |
| Mar 2, 2015 at 13:59 | comment | added | hoffmale |
you could save a small amount of time if you change the check in the two outer for loops from i < a.length() to i < a.length - (longestA.second - longestA.first) (same for j and b.length()) since you won't need to process any matches smaller than your current longest one
|
|
| Mar 2, 2015 at 13:40 | comment | added | hoffmale | Oh yeah, O(n^3) it is... had a different approach in mind that would've taken O(n^4), but that one is kinda useless by now xD | |
| Mar 2, 2015 at 13:27 | comment | added | ror3d | I believe it should be more like O(n^3) at worst case, at least with my algorithm it is. Anyway, I'm sure something can be done to improve it, like some kind of tree search, but I'm not sure how it would be implemented. | |
| Mar 2, 2015 at 13:25 | history | edited | ror3d | CC BY-SA 3.0 |
edited body
|
| Mar 2, 2015 at 13:21 | comment | added | hoffmale | Well, the complexity of the task required should be around O(n^4) to O(n^5), so long run times are a given | |
| Mar 2, 2015 at 12:59 | comment | added | ror3d | I'm really sorry it's such a bad solution. I've been searching for an algorithm to accomplish this in better time, but didn't find anything for now... | |
| Mar 2, 2015 at 12:22 | history | answered | ror3d | CC BY-SA 3.0 |