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

@Dani · Регистрация: 11.08.2011

Author24 — интернет-сервис помощи студентам

Возникла ситуация:
где бы я не читал разбор, немного непотно, как работает префикс-функция? Объясните, а что не пойму, попрошу изложить детальнее.

код префикс-функции

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;
}

@kzru_hunter · 21.12.2011, 14:27

код бредовый по-моему, но рабочий.
не пойму, что делает в нем k = p[k-1];

как я понял, из этого цикла можно выйти только кода k будет равен нулю:

C++

1 2	while ( (k > 0) && (s[k] != s[i]) ) k = p[k-1];

потому как я проверял ручным способом и пытался найти такой текст при котором после k = p[k-1]
k все ещё было бы больше нуля и s[k] стало бы равно s[i], что привело бы выходу из цикла. но увы, не удалось,т.к. если, например, в какой-то момент k>0 и попадаем в этот цикл и, например, s[k] = 'H', то после выполнения k = p[k-1], k изменится, но s[k] так и останется равным 'H'.

вот мой код, рабочий, проверял, оказался немножко быстрее, чем на википедии:

C++

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

@tennisru · 21.12.2011, 14:36

есть книга Окулов : алгоритмы обработки строк, там понятно описано

@kzru_hunter · 21.12.2011, 16:32

вообще, достаточно вот тут среди всего бреда, который мало кто поймет, взглянуть вот на это, и всё станет понятно:

Например, для строки 'abcdabscabcdabia' префикс-функция будет такой: π(abcdabscabcdabia)='0000120012345601'.
вычисление будет таким:
'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;

Добавлено через 42 минуты
Был не прав насчет кода, строку на википедии не совсем удачную выбрали, из-за чего неправильно понял алгоритм. В этой строке 'aabaaab' как раз учитывается тот момент, про который ругался в предыдущем посте. Для этой строки префикс-функция равна: [0,1,0,1,2,2,3] (смутить может предпоследняя цифра).

Добавлено через 1 час 5 минут
Dani предыдущий пост не воспринимай серьезно, там я неправильно написал да и код тоже неправильный из-за того, что не полностью понял алгоритм (кое какой момент смутил, как раз в том посте и ругался из-за него).
Вообщем, возьми строку "aabaaab", про которую писал выше и попробуй понять, как получить из неё префикс-функцию [0,1,0,1,2,2,3].

@tennisru 13 / 13 / 2 Регистрация: 10.09.2011 Сообщений: 179
	21.12.2011, 14:36	3
	есть книга Окулов : алгоритмы обработки строк, там понятно описано 1

@kzru_hunter 1123 / 794 / 101 Регистрация: 01.02.2011 Сообщений: 1,879 Записей в блоге: 1
	21.12.2011, 16:32	4
	вообще, достаточно вот тут среди всего бреда, который мало кто поймет, взглянуть вот на это, и всё станет понятно: Например, для строки 'abcdabscabcdabia' префикс-функция будет такой: π(abcdabscabcdabia)='0000120012345601'. вычисление будет таким: '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; Добавлено через 42 минуты Был не прав насчет кода, строку на википедии не совсем удачную выбрали, из-за чего неправильно понял алгоритм. В этой строке 'aabaaab' как раз учитывается тот момент, про который ругался в предыдущем посте. Для этой строки префикс-функция равна: [0,1,0,1,2,2,3] (смутить может предпоследняя цифра). Добавлено через 1 час 5 минут Dani предыдущий пост не воспринимай серьезно, там я неправильно написал да и код тоже неправильный из-за того, что не полностью понял алгоритм (кое какой момент смутил, как раз в том посте и ругался из-за него). Вообщем, возьми строку "aabaaab", про которую писал выше и попробуй понять, как получить из неё префикс-функцию [0,1,0,1,2,2,3]. 1