Гранню (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 (|S| ≤ 10^6
).
Виведіть довжину найбільшої грані.