Strings

В тази секция ще разгледаме как да работим ефективно със символни низове - намиране на повтарящи се такива, сравняване на подстрингове, намиране дали даден стринг се среща като подстринг в друг, и т.н. Ще разгледаме основните стрингови алгоритми - хеширане и Кнут-Морис-Прат - като и по-сложни приложения чрез структури данни: Хештаблица, Merkle Tree, префиксно дърво (Trie) и суфиксно дърво, както и Ахо-Корасик.

Темите, които ще са ви полезни, за да се справите с повечето стрингови задачи, са: Алгоритъм на Кнут-Морис-Прат, Хеширане, Хештаблица, Префиксно Дърво, Суфиксно Дърво, Суфиксен Масив, и Алгоритъм на Ахо-Корасик.

Тук се покриват относително малко от изброените алгоритми и структури данни, така че ако искате да се чувствате сигурни, е хубаво да погледнете и седните задачи: SUB_PROB, SARRAY, PHONELST, LCS.