Theory and Tasks for Students - Spring 2019
Алгоритмы на строках

Существует ряд простых задач, касающихся строк и массивов, для решения которых часто имеются встроенные методы. Однако, прежде чем их свободно использовать необходимо узнать, как они работают.

Сравнение строк

Сравнение строки происходит при помощи обычного оператора сравнения, за которым стоит достаточно простой код: def equals(a, b) : if (len(a) != len(b)) : # строки разной длины однозначно не равны return False; for i in range(len(a)) : if (a[i] != b[i]) : # если хотя бы один символ не совпадает return False; # строки не равны return True; # таким образом, строки одинаковой длины и все символы совпадают => они равны Такой алгоритм совершает в худшем случае N операций, если длина обеих строк - N символов. Оценка сложности алгоритма обозначается O(N) - это значение может быть относительно грубым и обычно рассчивается исходя "наихудшего" варианта развития событий, константные значения обычно опускаются. Оценка сложности этого алгоритма в лучшем случае - O(1) .

Кроме проверки на равенство строки можно сравнивать почти как числа - по-символьно. Есть несколько вариантов реализации, они дают разные результаты. Один алгоритм сравнивает символы слева направо и позволяет при сортировке выстроить строки в лексикографическом порядке - т.е. алфавитном: def compare(a, b) : # обычно такие функции возвращают разность (a - b) или одно из трёх значений: 1, 0, -1 n = min(len(a), len(b)); for i in range(n) : if (a[i] != b[i]) : if (a[i] > b[i]) : # сравнение символов производится по их коду, т.е. 'a' > 'A' return 1; else : return -1; if (len(a) > len(b)) : return 1; elif (len(a) < len(b)) : return -1; else : return 0; При такой реализации строка "2" будет больше чем "10" . Если требуется сравнивать строковые представления чисел, в алгоритме следует поставить сравнение длин строк в самое начало.

Поиск подстроки в строке

Встроенный метод - index . В общем случае он выполняет код, подобный следующему: def index(what, where) : flag = True; n = len(where) - len(what) + 1; for i in range(n) : # перебор индексов начала подстрок flag = True; for j in range(len(what)) : # перебор индексов искомой строки if (where[i + j] != what[j]) : # если хотя бы один символ не совпал с проверяемой подстрокой flag = False; break; if (flag) : # если все символы совпали return i; # возвращается индекс начала подстроки return -1; # подстрока не была найдена Встроенный метод вызывает от самой строки "abcde".index("cd") , в которой будет производиться поиск, и может принимать различные другие аргументы, как, например, индекс, с которого следует начинать поиск или сколько символов строки стоит проверять. Сложность такого алгоритма - порядка O(N2) , если считать, что обе строки имеют длину в N символов. Точнее оценка O((N-M)M)=O(NM-M2) , если длины исходной и искомой строк N и M соответственно. Таким образом, если у вас текст из порядка 106 символов и в нём требуется найти 100 подстрок по 100 символов, такой алгоритм должен будет совершить порядка 1010 операций - для сравнения, процессор компьютера может выполнять в районе 108 простейших операций в секунду. Поэтому для решения задачи поиска в заведомо большом тексте используется другой - более сложный - алгоритм.

Объединение строк

Встроенный метод - join . В других языках он может называться implode или glue . def join(glue, arr) : res = str(arr[0]); for i in range(1, len(arr)) : res += glue + str(arr[i]); return res; Этот метод перебирает все элементы массива и вставляет "строку-клей" между ними. Это бывает необходимо при более жёстких форматах вывода, когда, например, в файле после последнего элемента массива в строке не должно быть разделительного символа, а только перевод строки. В таком случае обычный подход даст немного другой результат: for item in arr : print(item, end = ", "); # вывод будет такой: 1, 2, 3, 4, Важно, что встроенный метод вызывается от строки-клея следующим образом: "separator".join(arr); . Так же во встроенном методе используется более оптимальный способ конкатенации строк, так как это достаточно дорогая операция: выделяется память под новый результат, все данные копируются туда, память с предыдущей строкой освобождается.

Разделение строки

Встроенный метод - split(). def split(separator, arg, rmEmpty = False) : # флаг rmEmpty показывает, убирать пустые результаты или нет res = []; buffer = ""; for c in arg : if (c == separator) : # если очередной символ - разделитель, значит мы на границе "слова", надо его добавить if ((rmEmpty && (len(buffer) != 0)) or (not removeEmpty)) : res.append(buffer); buferr = ""; else : # иначе добавляем в буфер buffer += c; return res; Этот метод несколько усложняется, если в качестве разделителя должен выступать не один символ, а целая строка.