|
|
back to boardwith a basic LCP and using not a fast prefix sort you might solve 1590 in 0.45 seconds on java 1.8 Posted by esbybb 15 Sep 2015 15:24 String s = scanner.next(); TreeSet<String> c = new TreeSet<String>(); for (int i=0; i<s.length(); i++) { c.add(s.substring(i)); } int L = c.size() + 1; long total = L - c.first().length(); while(c.size()>1) { String first = c.pollFirst(); String second = c.first(); int lcp = LCP(first, second); total+= L - second.length() - LCP(first, second);; } System.out.println(total); Re: with a basic LCP and using not a fast prefix sort you might solve 1590 in 0.45 seconds on java 1.8 Posted by esbybb 15 Sep 2015 15:25 static int LCP(String s1, String s2) { int l = 0; int j = Math.min(s1.length(), s2.length()); for (int i=0; i<j; i++) { if (s1.charAt(i)!=s2.charAt(i)) break; else l++; } return l; } |
|
|