Решение задачи 21.
Для решения данной задачи введем так называемую функцию отказов F(j), принимающей целочисленные значения [ Ахо А. и др. Построение и анализ вычислительных алгоритмов., М., 1979, с.386]. Функция F задается так: F(j) -- наибольшее число s<j, для которого A1 A2 ... As -- суффикс цепочки A1, A2, ..., Aj, т.е.
A1 A2 ... As = Aj-s+1 Aj-s+2 ... Aj
Если такого s=>1 нет, то F(j)=0.
Определим функцию F(m)(j) следующим образом:
1) F(1) (j)=F(j)
2) F(m) (j)=F(F(m-1) (j)) для m>1.
Будем вычислять функцию F итеративно. По определению F(1)=0.
Допустим, что вычислены F(1), F(2), ... , F(j). Пусть F(j)=i. Чтобы вычислить F(j+1) исследуем Aj+1 и Ai+1 . Если Aj+1 = Ai+1 , то
F(j+1)=F(i)+1 ,
поскольку
A1 A2 ... Ai Ai+1 = Aj-i+1 Aj-i+2 ... Aj Aj+1 .
Если Aj+1 <> Ai+1 , то тогда надо найти наибольшее значение i, для
которого
A1 ... Ai = Aj-i+1 ... Aj и Ai+1 = Aj+1 ,
если такое i существует. Если такого i нет, то очевидно, что F(j)=0. Пусть i1 , i2 , ... - наибольшее, второе по величине и т.д. значения i, для которых
A1 A2 ... Ai = Aj-i+1 ... Aj .
С помощью простой индукции убедимся, что
i1 =F(j), i2 =F(i1)=F(2)(j), ..., ik =F(ik-1)=F(k)(j), ....
Итак, в случае Aj+1 <> Ai+1 находим наименьшее m, для которого либо
1) F(m)(j)=u и Aj+1 = Au+1 , и полагаем тогда F(j+1)=u+1,
либо
2) F(m)(j)=0 и Aj+1<> A1, и тогда F(j+1) полагаем равным 0.
Алгоритм вычисления F следующий:
begin
F[1]:=0;
for j:=2 to n do
begin
i:=F[j-1];
while ( A[j]<>A[j+1] ) and ( i>0 ) do
i:=F[i];
if ( A[j]<>A[i+1] ) and ( i=0 )
then F[j]:=0
else F[j]:=i+1;
end;
end.
Этот алгоритм вычисляет F за O(n) шагов. Чтобы доказать это,
покажем, что сложность оператора while при работе программы (пропорциональная числу уменьшений значения i оператором i:=F[i]) линейно зависит от N.
Единственный способ увеличить i в этом фрагменте программы -это выполнить оператор F[j]:=i+1 в третьей от конца программы строке. Этот оператор может выполняться не более N-1 раза, следовательно, и уменьшение i в операторе while может произойти не более N раз. Остальная часть алгоритма имеет сложность O(n), и поэтому и весь алгоритм имеет сложность O(n).
Итак, мы вычислили F(n)=U, это означает, что
A1 A2 ... AU = A ... AN-U+1 (*)
Для того, чтобы последовательность
A1 ... AN
была периодической необходимо и достаточно, чтобы длина общей части двух строк в (*)
AN-U+1 ... AU
была кратна длине периода (в качестве периода последовательности тут выступает строка A1 ... AN-U ).
Действительно, если A1 ... AN-U = AN-U+1 ... A2(N-U) , то по
свойству (*) и AN-U+1 ... A2(N-U) = A2(N-U)+1 ... A3(N-U) и т.д.
Для окончательного решения задачи
1) найдем длину l перекрывающейся части строк в (*)
l=U-(N-U+1)+1 =2*U-n;
в случае l<=0 последовательность A1 ... AN непериодическая. Стоп.
2) Если l>0 , то проверим, делится ли нацело l на длину периода (т.е. на N-U)
l mod (N-U) = (2U-N) mod (N-U) = - ((N-U)-U) mod (N-U) =
= U mod (N-U) = R
Если R=0, то последовательность периодическая с периодом A1 ... AN-U ,
иначе - нет.
|
