WikiSort.ru - Не сортированное

Пре́фикс-фу́нкция от строки ${\displaystyle S}$ и позиции ${\displaystyle i}$ в ней — длина ${\displaystyle k}$ наибольшего префикса подстроки ${\displaystyle S[1..i]}$ , который одновременно является суффиксом этой подстроки. То есть в начале подстроки ${\displaystyle S[1..i]}$ длиной ${\displaystyle i}$ нужно найти такой префикс максимальной длины ${\displaystyle k<i}$ , который был бы суффиксом данной подстроки ${\displaystyle \left(S[1..k]==S\left[(i-k+1)..i\right]\right)}$ .

Обозначается ${\displaystyle \pi (S,i)}$ ; где ${\displaystyle S\in \Sigma ^{+}}$  — строка; ${\displaystyle 1\leqslant i<\left|S\right|}$  — длина подстроки в S. Считают, что ${\displaystyle \pi (S,1)=0}$ .

Часто префикс-функцию определяют в векторной форме:

Пре́фикс-фу́нкция от строки ${\displaystyle S\in \Sigma ^{+}}$ есть вектор ${\displaystyle \pi (S)\in \mathbb {Z} ^{\left|S\right|-1}}$ , каждый ${\displaystyle i}$ -ый элемент которого равен ${\displaystyle \pi (S,i)}$ .

Например, для строки 'abcdabscabcdabia' префикс-функция будет такой: π(abcdabscabcdabia)='0000120012345601'.

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

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

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

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

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

1. При ${\displaystyle S[i+1]=S[k+1]}$  — положить ${\displaystyle \pi (S,i+1)=k+1}$ .
2. Иначе при ${\displaystyle k=0}$  — положить ${\displaystyle \pi (S,i+1)=0}$ .
3. Иначе — установить ${\displaystyle k:=\pi (S,k)}$ и перейти к пункту 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 представляет собой внутренний цикл, время вычисления префикс-функции оценивается как ${\displaystyle O(|S|)}$ . Докажем это.

Все ${\displaystyle i}$ делятся на:

1. Увеличивающие ${\displaystyle k}$ на единицу. Цикл проходит одну итерацию.
2. Не изменяющие нулевое ${\displaystyle k}$ . Цикл также проходит одну итерацию. Случаев 1 и 2 в сумме не более ${\displaystyle \left|S\right|-1}$ штук.
3. Не изменяющие или уменьшающие положительное ${\displaystyle k}$ . Поскольку внутри цикла значение ${\displaystyle k}$ может только уменьшаться, а увеличение ${\displaystyle k}$ возможно лишь на единицу, то суммарно значение ${\displaystyle k}$ не может уменьшиться более, чем ${\displaystyle \left|S\right|-2}$ раза, что и ограничивает количество срабатываний внутреннего цикла.

Итого алгоритм требует не более ${\displaystyle 2\left|S\right|}$ итераций, что доказывает порядок скорости ${\displaystyle O(\left|S\right|)}$ . «Худшим» для алгоритма является случай обработки строки вида 'aa…ab'.

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

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

public static List<Integer> compute_prefix_function(String s) {
    int len = s.length();
    List<Integer> p = new ArrayList<>(); // значения префикс-функции
    for (int i = 0; i < len; ++i) {      // заполнение листа нулями default
        p.add(0);
    }
                                         // индекс листа соответствует номеру последнего символа аргумента
    int k = 0;
    for (int i = 1; i < len; ++i) {
        while ((k > 0) && (s.charAt(k) != s.charAt(i)))
            k = p.get(k - 1);
        if (s.charAt(k) == s.charAt(i))
            ++k;
        p.set(i, k);
    }
    return p;
}

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

def prefix(s):
    v = [0]*len(s)
    for i in range(1,len(s)):
        k = v[i-1]
        while k > 0 and s[k] != s[i]:
            k = v[k-1]
        if s[k] == s[i]:
            k = k + 1
        v[i] = k
    return v

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

prefix :: String -> [Int]
prefix [] = []
prefix str@(_:t) = 
    go 0 0 str t []
  where 
    go vlen _  []       _       v       = reverse v
    go vlen k s@(si:ssi) (sk:ssk) v 
        | si == sk  = go (vlen+1) (k + 1)  ssi    ssk  ((k+1):v)
        | k  == 0   = go (vlen+1)  0       ssi    str  (0:v)
        | otherwise = 
            let
               k' = v!!(vlen-k)
            in
               go  vlen k' s  (drop k'  str)  v

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 1 ноября 2013 года.