Префикс-функция

Пре́фикс-фу́нкция от строки (обозначается $\pi(S,i)~$; $S \in \Sigma^+$; $2 \leqslant i \leqslant \left| S \right|$) — длина наибольшего префикса строки $S[1 \ldots i]$, который не совпадает с этой строкой и одновременно является её суффиксом.

Часто префикс-функцию записывают в виде вектора длиной $\left| S \right|-1$. Например, для строки 'abcdabscabcdabia' префикс-функция будет такой: π(abcdabscabcdabia)='0000120012345601'. Иногда для полноты считают, что $\pi(S,1)=0~$.

Эта функция используется, например, в алгоритме Кнута — Морриса — Пратта.

Алгоритм вычисления

Символы строк нумеруются с 1.

Пусть $\pi (S,i)=k$. Попробуем вычислить префикс-функцию для $i+1$.

Если $S[i+1]=S[k+1]$, то, естественно, $\pi(S,i+1)=k+1$. Если нет — пробуем меньшие суффиксы. Очевидно, что $S[1 \ldots \pi(S,k)]$ также будет суффиксом строки $S[1 \ldots i]$, а для любого $j \in (k,i)$ строка $S[1 \ldots j]$ суффиксом не будет. Таким образом, получается алгоритм:

1. При $S[i+1]=S[k+1]$ — положить $\pi(S,i+1)=k+1$.
2. Иначе при $k=0$ — положить $\pi(S,i+1)=0$.
3. Иначе — установить $k:=\pi(S,k)$, GOTO 1.

Для строки 'abcdabscabcdabia' вычисление будет таким:

'a'!='b' => π=0;
'a'!='c' => π=0;
'a'!='d' => π=0;
'a'=='a' => π=π+1=1;
'b'=='b' => π=π+1=2;
'c'!='s' => π=0;
'a'!='c' => π=0;
'a'=='a' => π=π+1=1;
'b'=='b' => π=π+1=2;
'c'=='c' => π=π+1=3;
'd'=='d' => π=π+1=4;
'a'=='a' => π=π+1=5;
'b'=='b' => π=π+1=6;
's'!='i' => π=0;
'a'=='a' => π=π+1=1;

Скорость работы

Несмотря на то, что пункт 3 представляет собой внутренний цикл, время вычисления префикс-функции оценивается в $O(S)$. Докажем это.

Все $i$ делятся на:

1. Увеличивающие $k$ на единицу. Цикл проходит одну итерацию.
2. Не изменяющие нулевое $k$. Цикл также проходит одну итерацию. Случаев 1 и 2 (в сумме) не более $\left|S\right|$ штук.
3. Не изменяющие или уменьшающие положительное $k$. Если обозначить $\pi(S,i)=k_1$, $\pi(S,i+1)=k_2 \leqslant k_1$, то каждому такому случаю должны предшествовать как минимум $k_1 - k_2$ случаев 1. При этом количество сработавших GOTO 1 не превышает $k_1 - k_2 + 1$, что в сумме даёт не более $2\left|S\right|$ срабатываний.

Итог: цикл отрабатывает не более $3\left|S\right|$ итераций. Оценка явно завышенная, тем не менее, доказывающая порядок скорости $O(S)$.

Пример реализации на C++

vector<int> compute_prefix_function(const string& s) {
        int len = s.length();
        vector<int> p(len); // значения префикс-функции
                          // индекс вектора соответствует номеру последнего символа аргумента
        p[0] = 0; // для префикса из нуля и одного символа функция равна нулю
 
        int k = 0;
        for(int i = 1; i < len; i++) {          
                while ( (k > 0) && (s[k] != s[i]) ) 
                        k = p[k-1]; 
                if (s[k] == s[i])
                        k++;
                p[i] = k;
        }
        return p;
}

Пример реализации на Delphi

type Arr = array of LongInt;
function compute_prefix_function(s:string):Arr;
var k,i,l:LongInt;
begin
  l := Length(s);
  SetLength(Result, 1 + l);
  Result[0] := 0;
  Result[1] := 0;
  k := 0;
  for i := 2 to l do
  begin
    while (k > 0) and (s[k+1] <> s[i]) do
      k := Result[k];
    if s[k+1] = s[i] then
      Inc(k);
    Result[i] := k;
  end;
end;

Пример реализации на Haskell

computePrefixFn :: String -> [Int]
computePrefixFn str = helper 0 1 [0]
  where
    helper :: Int -> Int -> [Int] -> [Int]
    helper i k results
      | k == length str = results
      | otherwise =
        if (str !! i) == (str !! k)
          then helper (i+1) (k+1) (results ++ (ncur : []))
          else helper 0     (k+1) (results ++ (0    : []))
      where cur = last results
            ncur = cur + 1