чати довжину рядка .
Визначення [1]. Слово, яке не містить жодної букви, називається порожнім. Порожнє слово зазвичай позначається буквою . .
Визначення [1]. Слово називається префіксом слова , якщо є таке слово , що . Причому саме слово є префіксом для самого себе, так як знайдеться нульове слово , що .
Приклад: слово asd є префіксом слова asdqwe.
Визначення [1]. Слово називається суфіксом слова , якщо є таке слово , що . Аналогічно, слово є суфіксом самого себе.
Приклад: слово qwe є суфіксом слова asdqwe.
Визначення [1]. Слово називається підрядком рядка , якщо знайдуться такі рядки і , що . При цьому називається лівим, а - правим крилом підрядка. Підрядком може бути й саме слово. Іноді при цьому слово називають входженням в слово . Серед усіх входжень слова в слово , входження з найменшою довжиною свого лівого крила називають першим або головним входженням. Для позначення входження використовують позначення .
Приклад: слова asd і qwe є підрядками слова ryrqwetrasdyrt.
Визначення [5]. Складність алгоритму - залежність обсягу роботи, виконуваної алгоритмом від розміру вхідних даних. Причому, обсяг роботи зазвичай вимірюється абстрактними поняттями часу і простору, званими обчислювальними ресурсами. Тобто складність алгоритму - це кількість часу, необхідне для виконання алгоритму, та обсяг видатків при цьому пам'яті. Облік пам'яті зазвичай ведеться за обсягом даних. Час же розраховується у відносних одиницях так, щоб ця оцінка була однаковою для процесорів з різною частотою. p align="justify"> Існують дві характеристики складності алгоритмів - тимчасова і емкостная. p align="justify"> Тимчасова складність підраховується у виконуваних процесором командах: кількість арифметичних операцій, порівнянь і посилань.
Ємкісна складність визначається обсягом витраченої процесором пам'яті: кількість змінних, елементів масивів і рядків. p align="justify"> Ефективність алгоритму оцінюється за допомогою підрахунку часу, витраченого програмою для ...
