ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1590. Шифр Бэкона

with a basic LCP and using not a fast prefix sort you might solve 1590 in 0.45 seconds on java 1.8
Послано esbybb 15 сен 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
Послано esbybb 15 сен 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;
    }