ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1590. Bacon’s Cipher

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: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;
    }