Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.73
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
17.12.2011, 19:20     Префикс-функция #1
Возникла ситуация:
где бы я не читал разбор, немного непотно, как работает префикс-функция? Объясните, а что не пойму, попрошу изложить детальнее.

код префикс-функции
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
 Аватар для kzru_hunter
1084 / 759 / 58
Регистрация: 01.02.2011
Сообщений: 1,771
Записей в блоге: 1
21.12.2011, 14:27     Префикс-функция #2
код бредовый по-моему, но рабочий.
не пойму, что делает в нем 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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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
13 / 13 / 1
Регистрация: 10.09.2011
Сообщений: 179
21.12.2011, 14:36     Префикс-функция #3
есть книга Окулов : алгоритмы обработки строк, там понятно описано
kzru_hunter
 Аватар для kzru_hunter
1084 / 759 / 58
Регистрация: 01.02.2011
Сообщений: 1,771
Записей в блоге: 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].
Yandex
Объявления
21.12.2011, 16:32     Префикс-функция
Ответ Создать тему
Опции темы

Текущее время: 11:36. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru