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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Пре́фикс-фу́нкция от строки (обозначается ; где - строка; - длина префикса в S) — длина наибольшего префикса строки , (исключая вырожденный случай, где префикс совпадает с этой строкой, т.е. ), который одновременно является её суффиксом.

Т.е. в строке и её префиксе длиной нужно найти такой префикс максимальной длины, который был бы суффиксом данной строки.

Часто префикс-функцию записывают в виде вектора длиной . Например, для строки 'abcdabscabcdabia' префикс-функция будет такой: π(abcdabscabcdabia)='0000120012345601'. Иногда для полноты считают, что .

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

Алгоритм вычисления[править | править вики-текст]

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

Пусть . Попробуем вычислить префикс-функцию для .

Если , то, естественно, . Если нет — пробуем меньшие суффиксы. Очевидно, что также будет суффиксом строки , а для любого строка суффиксом не будет. Таким образом, получается алгоритм:

  1. При  — положить .
  2. Иначе при  — положить .
  3. Иначе — установить , 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;

Чуть более интересный пример - для строки 'abcdabcabcdabcdab' вычисление будет таким:

1  S[1]='a', k=π=0;
2  S[2]='b'!=S[k+1] => k=π=0;
3  S[3]='c'!=S[1] => k=π=0;
4  S[4]='d'!=S[1] => k=π=0;
5  S[5]='a'==S[1] => k=π=1;
6  S[6]='b'==S[2] => k=π=2;
7  S[7]='c'==S[3] => k=π=3;
8  S[8]='a'!=S[4] => k:=π(S, 3)=0, S[8]==S[1] => k=π=1;
9  S[9]='b'==S[2] => k=π=2;
10 S[10]='c'==S[3] => k=π=3;
11 S[11]='d'==S[4] => k=π=4;
12 S[12]='a'==S[5] => k=π=5;
13 S[13]='b'==S[6] => k=π=6;
14 S[14]='c'==S[7] => k=π=7;
15 S[15]='d'!=S[8] => k:=π(S, 7)=3, S[15]==S[4] => k=π=4;
16 S[16]='a'==S[5] => k=π=5;
17 S[17]='b'==S[6] => k=π=6;

И результат таков: '00001231234567456'.

Скорость работы[править | править вики-текст]

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

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

  1. Увеличивающие на единицу. Цикл проходит одну итерацию.
  2. Не изменяющие нулевое . Цикл также проходит одну итерацию. Случаев 1 и 2 (в сумме) не более штук.
  3. Не изменяющие или уменьшающие положительное . Если обозначить , , то каждому такому случаю должны предшествовать как минимум случаев 1. При этом количество сработавших GOTO 1 не превышает , что в сумме даёт не более срабатываний.

Итог: цикл отрабатывает не более итераций. Оценка явно завышенная, тем не менее, доказывающая порядок скорости .

Пример реализации на 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;

Пример реализации на Ruby[править | править вики-текст]

def prefix s
  n = s.length-1
  p = Array.new(n,0)
  n.times do |i|
    i+=1
    j = p[i-1]
    while j > 0 && s[i] != s[j]
      j = p[j-1]
    end
    j+=1 if s[i]==s[j]
    p[i] = j
  end
  return p
end