Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, watchmaker, Вы писали:
К>>>но КАЖЕТСЯ, что мы действительно имеем дело с непересекающимися классами, поэтому можем суммировать как есть.
W>>Круто, но процитированные классы таки пересекаются.
W>>Например, строку "ABABA" можно получить из "ABAB" добавлением "A", либо из "ABA" добавлением суффикса "BA".
W>>То есть в этой уникальной строке повторяются разные подстроки: "ABABA" и "ABABA", и она оказывается посчитанной дважды.
К>Да, именно это у меня и вышло в брутфорсе.
К>Получается, что надо дробить класс Q(n) строк без повторов длины n на подклассы вида Q(n, t1,t2,...) где ti — длина паразитного повтора
К>К>Подкласс t=2
К>xxxABA + BA = xxxABABA
К> --==
К>Подкласс t=3
К>xxxABCA + BCA = xxxABCABCA
К> ---===
К>Подкласс t=4
К>xxxABCDA + BCDA = xxxABCDABCDA
К> ----====
К>Подкласс t=2,4 --==
К>xxxABACA + CA = xxxABACACA
К>xxxABACA + BACA = xxxABACABACA
К> ----====
К>Подкласс t=2,5
К>xxxABCADA + DA
К>xxxABCADA + BCADA
К>Подкласс t=3,5
К>xxxABACDA + CDA
К>xxxABACDA + BACDA
К>
К>Тогда формула будет выглядеть вот так:
К>К>Q(n) = Q(n-1)*a
К> - Q(n-1) - повторы длины 1
К> - Q(n-2) + Q(n-2,2) - поскольку мы
К> - Q(n-3) + Q(n-3,2) + Q(n-3,3)
К> - Q(n-4) + Q(n-4,2) + Q(n-4,3) + Q(n-4,4) - Q(n-4,2,4)
К> . . .
К>
К>(если ничего не путаю)
К>Длины паразитных повторов — это положения вхождений последней буквы, с конца.
К>И вот это мне очень не нравится: чтобы за ними проследить, нам придётся не расписывать формулу для каждого подкласса
К>Q(n,t1) = Q(n-1,t1)*a + ... — ...,
К>а в завуалированной форме рожать все строки. А их, понятное дело, экспонента по основанию мощности алфавита (a). (Ну, ближе к (a-1), но всё равно не сахар).
Что-то похожее на принцип включения-исключения. Но как его применить до конца пока не приходит в голову.
