2 ms·
That would be O(n^2) though, where n is the max length of the strings to compare, right?
by kstrauser 2y ago
That would be O(n^2) though, where n is the max length of the strings to compare, right?
- sponaugle 2y agoMy current method is O( (n/h)^2 ) where h is the hash size, which is really O(n^2) for n>>h. I'll have to think about this to see if it would be better.
- im3w1l 2y agoNo, it's possible to do much better https://www.geeksforgeeks.org/sliding-window-maximum-maximum-of-all-subarrays-of-size-k/ https://www.geeksforgeeks.org/sliding-window-maximum-maximum... Edit: It should also be mentioned that due to the conjectured normality of pi, comparing two sequences will on average terminate very quickly, just looking at one or two digits will be enough most of the time, so a comparison is expected O(1).
- sponaugle 2y agoIndeed, the comparison length is 90% one hit, 99% two hits, etc.