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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.73
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
#1

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

17.12.2011, 19:20. Просмотров 3135. Ответов 3
Метки нет (Все метки)

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

код префикс-функции
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;
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.12.2011, 19:20
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Префикс-функция (C++):

Префикс-функция - C++
Пишу программу для реализации префикс функции. Возник ступор... Дана строка: aabaaabaa Какой из вариантов правильный? а) 0 1 0 1...

постфикс и префикс в c++ - C++
Почему получилось в последнем выводе car3.vivod -1 #include &quot;stdafx.h&quot; #include&lt;iostream&gt; using namespace std; class Cars ...

Префикс L и русские буквы - C++
Простой файл: #include &lt;iostream&gt; #include &lt;locale&gt; using namespace std; int main() { setlocale(LC_ALL,...

Префикс наименования переменных - C++
изучаю код, пытаюсь приучить себя к стилю, разработчики используют префикс sz к типу LPCSTR, почему sz??? для переменных указателей...

Заменить префикс “пере” на “при” - C++
Если слово начинаетса с префикса “пере”, то заменить эго на “при”. помогите пожалуста=) програмирование задач оброботка рядков

Префикс __imp__ попадает в exe-шный модуль из DLL - C++
Помогите плз убрать префикс. Импортирую Переменные из Длл в екзешник, явным способом по книже Пецольда. Заголовочный файл созданый...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
kzru_hunter
1090 / 765 / 58
Регистрация: 01.02.2011
Сообщений: 1,779
Записей в блоге: 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;
}
1
tennisru
13 / 13 / 1
Регистрация: 10.09.2011
Сообщений: 179
21.12.2011, 14:36 #3
есть книга Окулов : алгоритмы обработки строк, там понятно описано
1
kzru_hunter
1090 / 765 / 58
Регистрация: 01.02.2011
Сообщений: 1,779
Записей в блоге: 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
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.12.2011, 16:32
Привет! Вот еще темы с ответами:

Возможно ли присвоить переменной типа string префикс 'L' при выводе - C++
Возможно ли присвоить переменной типа string префикс 'L' при выводе? Если да, то как. Проблема в том, что слово хранящееся в переменной...

Вывести на экран список слов, у которых есть префикс (несколько букв), которые задаются с клавиатуры - C++
Вывести на экран список слов, у которых есть префикс (несколько букв), которые задаются с клавиатуры.

Префикс "пере" заменить на "при" - C++
Если слово начинается с префикса &quot;пере&quot;, то заменить его на &quot;при&quot;. ПОМОГИТЕ С КОДОМ ПОЖАЛУЙСТА

Перегрузка операций: friend-функция или функция-член класса - C++
Здравствуйте, меня интересует вопрос, в чем разница при перегрузке операторов через operator и friend. Вот к примеру такой код. class...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
21.12.2011, 16:32
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru