amirnotch / calfunction Goto Github PK

Описание кода который решает задачку String Function Calculation:

1. Класс Suffix: Этот класс представляет суффикс строки. У него есть два свойства: Index, которое хранит начальный индекс суффикса в строке, и Rank, массив из двух элементов, который хранит ранги суффикса и следующего суффикса.

2. Класс SuffixComparer: Этот класс реализует интерфейс IComparer и используется для сравнения двух суффиксов.

3. Метод BuildSuffixArray: Этот метод строит суффиксный массив для данной строки. Он начинает с инициализации массива суффиксов, где каждый суффикс имеет ранг, равный его первому символу, и ранг следующего суффикса. Затем он сортирует суффиксы по их рангам и обновляет их ранги. Этот процесс повторяется, пока все суффиксы не будут отсортированы.

4. Метод LCP: Этот метод вычисляет массив наименьших общих префиксов для данной строки и ее суффиксного массива. Он начинает с инициализации массива invSuff и переменной k. Затем он проходит по строке и для каждого символа вычисляет длину общего префикса с следующим суффиксом и сохраняет его в массиве lcp.

5. Метод MaxValue: Этот метод вычисляет максимальное значение функции f(s)=∣s∣⋅∣set(s)∣ для всех подстрок данной строки. Он начинает с вычисления суффиксного массива и массива LCP для строки. Затем он проходит по массиву LCP и для каждого элемента вычисляет значение функции, умножая его на количество суффиксов, которые имеют такую же или большую длину общего префикса. Максимальное из этих значений является ответом.

6. Метод Main: Этот метод считывает строку из стандартного ввода, вычисляет максимальное значение функции с помощью метода MaxValue и выводит его в стандартный вывод.