|
|
вернуться в форумA simple solution using suffix arrays Послано 吕蒙子明 22 апр 2011 00:07 Well, the N is rather small that we can construct the suffix array for O(N^2logN) for example, we get all the suffix and sort it: a aa aaa then calculate the longest common prefix(LCP) between two neighbour string we get : 1 2 it means that: the substring "a" occurs 3 times (in string 1,2, LCP is "a",in string 2,3, LCP is "aa", which also contains "a") , and should be counted as once the substring "aa" occurs twice and it's also should be counted as once then the answer should be : 3 * (3 + 1) / 2 - 1 - 2 = 3 Re: A simple solution using suffix arrays Послано ASK 7 фев 2014 00:15 Re: A simple solution using suffix arrays i found the DC3 algorithm much easier to understand (and implement). and it is fast enough (even in scala) |
|
|