Məsələlər
Вершины неявного суффиксного дерева (Hard)
Вершины неявного суффиксного дерева (Hard)
Суффиксное дерево --- называется неявным, если оно содержит как неявный бор все суффиксы строки и при этом содержит минимальное количество вершин.
Например, неявное суффиксное дерево строки "\textbf{ababa}" выглядит так, как показано на рисунке ниже (в нем имеются \textbf{3} вершины):
\includegraphics{https://static.e-olymp.com/content/ed/ed33038b7499fcc2fb4e1260b9fb6af2827a235e.jpg}
\includegraphics{https://static.e-olymp.com/content/6e/6e88e8278140e885406abf29bb75383876e39a52.jpg}
Вам задана строка \textbf{s}, как конкатенация \textbf{k} копий строки \textbf{t}. То есть, \textbf{s = t + t + t + ... + t =} . Посчитайте, количество вершин в неявном суффиксном дереве строки \textbf{s}.
\InputFile
В первой строке записано целое число \textbf{k} (\textbf{1} ≤ \textbf{k} ≤ \textbf{10^9}). Во второй строке записана строка \textbf{t} (\textbf{1} ≤ \textbf{|t|} ≤ \textbf{10^5}). Строка \textbf{t} состоит только из маленьких латинских букв.
\OutputFile
Выведите единственное целое число --- количество вершин в неявном суффиксном дереве строки \textbf{s}.
Giriş verilənləri #1
1000 a
Çıxış verilənləri #1
2