Practicum1 К 21 не успел тесты сделать, но был полностью рабочий код, решающий задчу. 9) Даны а, буква x и натуральное число k. Вывести длину кратчайшего слова из языка L, содержащего подслово x^k.
Дп на стеке. В любой момент времени на стеке хранятся языки, можно добавить новый, и проделать операции над предыдущими 2. Для любого языка L на стеке выполняется следующее: l[i][0] - длина минимального слова, что оно содержит x^i, l[i][1] - длина минимального слова, что суффикс заканчивается на x^i, l[i][2] - длина минимального слова, что префикс начинается на x^i.
При чтении буквы с из строки добавим ее на стек:
- Если с == x, то у нас есть слово длины 1, в котором префикс/суффикс начинатся/заканчивается на x^1, ну и соответственно содержит x^1 тоже. Поэтому l[1][0] = l[1][1] = l[1][2] = 1; А также слово длины 1, в котором содержится x^0(+перфикс и суффикс) l[0][0] = l[0][1] = l[0][2] = 1.
- В противном случае имеем слово длины 1 в котором вообще нет буквы х. Поэтому только l[0][0] = l[0][1] = l[0][2] = 1.
+: При сложении 2 языков, чтобы поддерживать динамику просто возьмем минимум из 2 языков для каждого a[i][j], b[i][j]. (0 <= i <= k, 0 <= j <= 2)
Перемножение языков a, b: c = a.b; Поймем, как мог измениться ответ для с относительно a, b; Рассмотрим префиксы: x^i для a x^j для b c[i][2] = a[i][2] + b[j][0] // Префикс слова из а содержит вначале хотябы i букв x, и продолжается словом из b; c[min(i + j, k)][2] = a[i][0] + b[j][2] // Если есть такое слово в а, которое состоит целиком из x, и продолжается префиксом из x для слова из b; Аналогично для суффикса; Для "содержится": c[i][0] = min(c[i][0], a[i][0] + b[j][0]); c[j][0] = min(c[j][0], a[i][0] + b[j][0]); // Берем слово, содержащееся в a или b и дописываем, что нибудь из другого языка, тогда подслово x^i/x^j точно содержится в c Либо суффикс из a и префикс из b: c[min(i + j, k)][0] = min(c[min(i + j, k)][0], a[i][1] + b[j][2]);
Звезда клини: Более k раз нет смысла перемножать язык, так как x^k, если и получается, то получается не позднее k-ого шага. Поэтому a*, реализуем как a^k + a^k-1 + a^k-2 + ... + a^0.
Ответ для оставшегося языка L будет содержаться в l[k][0]