Задача №3353. Обратная префикс-функция (A+)
Для строки S определим ее префикс-функцию: \(\pi [i] = max(k|0 \leq k < i; S[1..k] = S[i - k + 1..i])\) для всех \(1 \leq i \leq N\), где \(N\) — длина строки. Например, для S = abacabaa ее префикс-функция имеет вид: [0, 0, 1, 0, 1, 2, 3, 1]. Ваша задача по заданной префикс-функции восстановить строку. В качестве символов строки разрешается использование \(M\) первых строчных букв латинского алфавита.
Входной файл состоит из одного или более набора входных данных. В первой строке каждого набора записаны два целых числа \(N\), \(M\) (\(N \geq 1\), \(1 \leq M \leq 26\)). Во второй строке записана последовательность целых чисел \(\pi [1]\), \(\pi [2]\), ..., \(\pi [N]\). Все числа в последовательности целые неотрицательные, не превосходящие \(10^6\). Сумма значений \(N\) по всем наборам не превосходит \(10^6\), количество наборов входных данных не превосходит \(10^5\).
Выведите в первую строку выходного файла YES если существует искомое слово и NO в противном случае. В случае положительного ответа выведите во вторую строку выходного файла выведите искомое слово. Если решений несколько, выведите любое.
8 3 0 0 1 0 1 2 3 1 1 1 10
YES abacabaa NO