- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <utility>
#include <sstream>
#include <assert.h>
using namespace std;
struct PeriodDescription{
size_t length, repeat_amount, last_items_amount;
/*friend ostream& operator<<(ostream& os, const PeriodDescription& s){
os<<" (PeriodDescription){"<<s.length<<", "<<s.repeat_amount<<", "<<s.last_items_amount<<"} ";
return os;
}*/
};
/*template<class C>
string co(C&& c){
ostringstream r;
r<<" (C) {";
copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(r, ", "));
r<<"}; ";
return move(r.str());
}*/
vector<PeriodDescription> find_repeat_sequences_since_begin(const string& sequence){
vector<PeriodDescription> result;
if(sequence.empty())
return result;
auto position_at_last_period=sequence.begin();
const char first_item = *position_at_last_period;
const auto after_last=sequence.end();
auto position_at_current_period = position_at_last_period;
while(true){
position_at_last_period=sequence.begin();
position_at_current_period = find(next(position_at_current_period), after_last, first_item);
PeriodDescription new_period {size_t(distance(position_at_last_period, position_at_current_period)), 1, 0};
while(position_at_current_period!=after_last && *position_at_last_period==*position_at_current_period){
++position_at_last_period; ++position_at_current_period;
if(++new_period.last_items_amount>=new_period.length){
new_period.last_items_amount = 0;
++new_period.repeat_amount;
}
}
if(new_period.repeat_amount==1 && new_period.last_items_amount==0)
return result;
result.push_back(new_period);
if(position_at_current_period==after_last)
return result;
}
}
vector<size_t> generate_FSM_failJumpIndices(const vector<PeriodDescription>& periodDescriptions, const size_t stringLength){
vector<size_t> r(stringLength+1);
for(const auto& pd : periodDescriptions){
for(size_t periodIndex=1; periodIndex<pd.repeat_amount; ++periodIndex)
for(size_t indexAtPeriod=0; indexAtPeriod<pd.length; ++indexAtPeriod)
r[(periodIndex*pd.length)+indexAtPeriod]=(periodIndex-1)*pd.length + indexAtPeriod;
for(size_t indexAtAfterPeriods=0; indexAtAfterPeriods<pd.last_items_amount; ++indexAtAfterPeriods)
r[pd.length*pd.repeat_amount+indexAtAfterPeriods]=pd.length*(pd.repeat_amount-1)+indexAtAfterPeriods;
}
return r;
}
vector<size_t> make_FSM_failJumpIndices(const string& sequence){
return generate_FSM_failJumpIndices(find_repeat_sequences_since_begin(sequence), sequence.size());
}
class FSM_for_find_equal_ranges{
size_t state;
vector<size_t> failJumpIndices;
string sequence;
string::const_iterator find_next(string::const_iterator checkPosition, const string::const_iterator last){
struct atReturn{
size_t& state;
~atReturn(){state = 0;}
}nullify{state};
if(checkPosition==last)
return last;
if(sequence.empty())
return next(checkPosition);
if(size_t(distance(checkPosition, last))<sequence.size())
return last;
while(true){
if(checkPosition==last)
return last;
if(*checkPosition==sequence[state])
++state;
else
state=failJumpIndices[state];
++checkPosition;
if(state>=sequence.size())
return prev(checkPosition, sequence.size());
}
}
public:
template<class T>
FSM_for_find_equal_ranges(T&& sequence):
Очередное собеседование. Пригласили на должность дельфина. Но оп отказался проходить собеседование на дельфи.
http://ideone.com/zp5CRb
Follow us!
Как можно было такую простую задачу запороть?
Это поиск подстроки в строке aлгоритмом Кнута–Морриса-Пратта.
Как можно было упороться, чтобы расписать её на большую часть алгоритма? Что он курил?
кто-то заработал геморрой, сидя на лекциях по дискретной математике с толстым томиком кнута, и теперь этот геморрой не дает покоя ни ему, ни кандидатам
> возле практики
сомнительно
> чисто "сосбеседовские"
Ну я не знаю, кем нужно быть, чтобы на собесе спрашивать Кнута-Морриса-Пратта. Маразм какой-то.
>> на дельфи пишется как
уж больно всё похоже на тред, где засветился тарас
+1. Я от алгоритма КМП помню только название ;)
P.S. Что-то мне кажется, что не на то они кандидатов проверяют, совсем не на то...
Аналогично. Если что, томик Кнута недалеко.
PS> емнип в жабе и шарпике даже КМП не осилили.
Две таблички сдвигов строятся в Алгоритме Бойера — Мура и поиск осуществляются в обратном порядке.
Конечно-конечно, всё перепутал. Ведь конечный автомат - это ахо-корасик.
Извините, но вы нам не подходите
Бугага. Копипаст с викижопии детектед.
Потому что криворуких макак, которые пилили стандартную либу тоже на собеседовании вот не спрашивали КМП.
Например сделать открывающий тег aaaa[...], а потом ищется закрывающий матчится таким же aaaa[..], но там стоит aaaa[..]b. Ограничений по размеру обычно там нет, потому можно заслать метров 100 и пусть CPU радуется квадратичной сложности.
Профит.
Тут надо код конкретного софта+реализация indexOf изучать на предмет подобного.
Как раз тут не так легко. Практически везде пофиксили (случайная соль к хешу при старте - иди подбирай) а в пыхе который многие обсирают стоит ограничение на размер запроса.
В жаве когда букет хеш-мапы пухнет, он превратится в дерево.
Потому сложность worst-case O(log(n))
Это не худший, это пиздец котёнку. Хешмап в таких условиях вообще не может работать.
А константный хеш - это все-таки правильный хеш, хоть и производительность падает до плинтуса.
> для равных значений получается разный хеш
Вы несете чушь, ибо совершенно потеряли нить обсуждения.
Речь о правильно написанном коде (хеш-функции, хеш-мапы), имеющих в большинстве случаев константную сложность.
Однако для них злоумышленник искусственно создает маловероятный worst-case O(N), с целью огранизации DOS.
Сортировки вот тоже O(N*log(N)) в среднем (подавляющее большинство случаев), однако многие из них скатываются в O(N*N) при определенных и маловероятных обстоятельствах.
Я знаю что оно жрёт память и много кэшпромахов, из-за которых оно в среднем вдвое тормознее хэша, зато стабильнее.
Нет. Я так считал лет 10 назад, когда плохо понимал как работают хеш-мапы.
>из-за которых оно в среднем вдвое тормознее хэша
Нет. "Вдвое" - это полнейший бред.
хеш - O(1). дерево - O(log(N)).
>В жаве когда букет хеш-мапы пухнет, он превратится в дерево.
Как тебе такой гибрид?
>префиксдерево
Оно в теории жрёт памяти меньше, чем любая другая структура, но на практике не оправдывает себя, обычное двоичное дерево его уделает.
> дерево - O(log(N)).
Очень умно, ага O(длина ключа) когда надо считаем единицей, а когда надо - логарифмом, ага.
Хеш на тяжелых объектах (большие немутабельные строки) обычно кешируется при создании в константу.
А если заранее запомнить типа "вот для строки, хранящейся вот тут - такой-то хеш" - так тогда нафиг хеш, можно просто брать ИД.
В случае дерева (BST), кол-во сравнений O(log(N)), ибо вложенность растёт пропорционально логарифму от числа элементов.
Префиксное же дерево, оно же бор, да O(len(search)), но на практике по производительности полная херня - наверное из-за произвольных выборок памяти, которые трудно предугадать.
А ничё, что каждое сравнение - это O(logN) в хадшем случае?
Я ж говорю, вы удобно устроились, когда надо - вы считаете длину ключа как логарифм, когда надо - не считаете вообще.
> но на практике по производительности полная херня
Если нужна алгоритмическая стабильность - то не херня.
>вы считаете длину ключа как логарифм
То я о BST.
>Если нужна алгоритмическая стабильность - то не херня.
Ну у хеша есть одно полезное свойство когда его сложность минимальна - если элементов в букете вообще нету, тогда сложность будет O(1), хотя в префиксе такое будет если нет слов, начинающихся на.
В противном случае, да ты прав O(len(search_text)
А, ну ты об этом уже сказал. Короче у trie идея красивая - безусловно, но в реальном железе оно плохо работает.
Всем похуй.
А вот возвращать разные значения хеш-функция не может по определению - она не будет хеш функцией в таком случае.
Он везде стоит. Каков его размер?
Кстати, кто поможет найти сплоит к питону?
Сказывают, что в йандексе вопрошают всякие-разные алгоритмы. КМП - среди них.
А вот в мылору, из тех же источников, задача про уточку.
Что за задача?
На всякий случай приведу текст. Источник не оригинальный, но условия неизменны, обычно.
„Есть озеро в форме круга. В центре озера находится утка, на краю озера находится лиса. Утка может двигаться по воде со скоростью v, лиса - по окружности озера со скоростью 4v. Утке нужно попасть на берег так, чтобы в этой точке не было лисы.”
Общая суть сводится к вопросу: возможно ли уточке попасть на берег, если да, то как.
А еще хорошая задача про 2(3, 4, ... n) термометров у которых есть предел прочности, и надо измерить максимальную температуру, которую они могут выдержать - от 0 до 1000 градусов, с шагом 10. При этом сделав минимальное число измерений.
Полезно для оптимизации поиска в каких-либо структурах, например данные на ленте которую нельзя перемотать назад, а надо делать полный цикл/оборот, то есть где штраф за превышение границы данных очень велик.
Есть. Кажется, оно около π.
слово "один" иногда можно заменить на "раз"
того пи+1 аолучается...
4.14159265