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

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

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
https://sites.google.com/site/yuta256/sais
is a good implementation of the suffix array
Re: A simple solution using suffix arrays
Послано akos tajti 20 июн 2014 20:54
i found the DC3 algorithm much easier to understand (and implement). and it is fast enough (even in scala)