Условие
Гранью (border, verge, brink) $br$ строки $S$ называется любой собственный префикс этой строки, равный суффиксу $S$.
Строка $S=abaababaabaab$ имеет две грани (не пустые): $ab$ и $abaab$. Строка $S=abaabaab$ также имеет две грани: $ab$ и $abaab$, но вторая грань — перекрывающаяся. Строка длины $n$ из повторяющегося символа, например $aaaaaaaa$ (или $a^8$), имеет $n-1$ грань. Для $S=a^8$ это грани: $a, aa, aaa, aaaa, aaaaa, aaaaaa, aaaaaaa$.
Понятие «собственный префикс» исключает грань, совпадающую с самой строкой.
Длина грани — это количество символов в ней.
Сделаем обобщение задачи. Пусть необходимо вычислить значения наибольших граней для всех подстрок $S[1..i] (i = 1..n)$ и сохранить их в массиве $br[1..n]$.
Найдите наибольшее значение грани в массиве наибольших граней $br$ для всех подстрок $S$.
Тесты
| Входные данные | Выходные данные | Комментарий |
| $abaabaab$ | 5 | $abaab$ в исходной строке |
| $abaababaabaab$ | 6 | $abaaba$ в подстроке abaababaabaab |
| $aaaaaaaa$ | 7 | $aaaaaaa$ в исходной строке |
| $YM$ | 0 | Грань отсутствует, т.к. префикс и суффикс не могут совпадать с самой строкой, а кроме $Y$ в качестве префикса и $M$ в качестве суффикса вариантов выбора нет |
| $&#%*%#&$ | 1 | $&$ в исходной строке |
| $15015105$ | 2 | $15$ в подстроке 15015105 |
Код задачи
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String S = sc.nextLine(); int answer = 0; // Длина наибольшей грани for(int i = 1; i < S.length() && S.length() - i > answer; i++) { int j = 0; /* Перебираем различные длины префиксов (суффиксов), пока не дойдем до длины 1 и пока можем встретить грань, длиннее хранящейся. i - первый символ очередного суффикса j - длина текущей грани и первый символ очередного префикса */ while(j < S.length() - i && S.charAt(j) == S.charAt(i + j)){ // Накапливаем длину, пока символы префикса и суффикса совпадают j++; } if (j > answer) answer = j; } System.out.print(answer); } } |
Решение
Отметим, что сохранять значение наибольших граней в массив, как указывается в условии, необязательно, так как значение длины максимальной грани можно обновлять по ходу нахождения граней подстрок.
В основе программы лежит алгоритм, идея которого заключается не в переборе подстрок с последующим поиском граней в них (так как это было бы очень ресурсозатратно), а в переборе смещений префикса и суффикса друг относительно друга и вычислении максимальной грани, которую можно получить в каждом из таких смещений. Цикл перебора выглядит следующим образом:
- Так как по условию грань не может совпадать со строкой, перебор начнем со случая, когда первый символ суффикса находится на второй позиции в строке, а первый символ префикса — на первой позиции. В каждой следующей итерации первый символ суффикса будет смещаться на одну позицию вправо, но первый символ префикса будет неизменно оставаться на первой позиции. Цикл продолжается до тех пор, пока не дойдем до случая, когда первый символ суффикса будет последним символом строки, и пока количество символов от начала суффикса до конца строки будет больше длины максимальной найденной на данный момент грани (это условие необязательно, но оно ускоряет работу программы, отбрасывая варианты, когда получить более длинную грань уже никаким образом не получится):
1234567for(int i = 1; i < S.length() && S.length() - i > answer; i++) {int j = 0;/*Перебираем различные длины префиксов (суффиксов), пока не дойдем до длины 1 и пока можем встретить грань, длиннее хранящейся.i - первый символ очередного суффиксаj - длина текущей грани и первый символ очередного префикса*/ - Начнем параллельно «двигаться» вправо по строке, проверяя на совпадение соответствующие символы префикса и суффикса и продолжая до тех пор, пока не наткнемся на различные символы или пока не дойдем до конца строки. При этом будем попутно накапливать значение длины текущей грани, пока пары символов совпадают.К примеру, если в очередной итерации первые символы префикса и суффикса — это первый и третий символы строки соответственно, то сначала проверим на совпадение символы на позициях 1 и 3, затем 2 и 4, 3 и 5 и т. д.
В виду того, что нумерация символов в строке начинается с нуля, переменная $j$ выполняет здесь одновременно роль первого символа префикса и длины текущей грани.123while(j < S.length() - i && S.charAt(j) == S.charAt(i + j)){ // Накапливаем длину, пока символы префикса и суффикса совпадаютj++;} - Сравним длину текущей грани с длиной максимальной грани и, если необходимо, обновим значение максимальной.
Отметим, что значение переменной $j$, получаемое в каждой итерации, представляет собой максимально возможную длину грани либо исходной строки (если проверки на совпадение пар символов закончились из-за достижения конца строки), либо подстроки, получаемой путем отбрасывания правой части исходной до того символа, на котором обнаружилось несовпадение.