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

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

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

Сравнение строки происходит при помощи обычного оператора сравнения, который в свою очередь вызывает метод Equals, за которым стоит достаточно простой код: bool Equals(string a, string b) { if (a.Length != b.Length) { // строки разной длины однозначно не равны return false; } for (int i = 0; i < a.Length; i++) { if (a[i] != b[i]) { // если хотя бы один символ не совпадает return false; // строки не равны } } return true; // таким образом, строки одинаковой длины и все символы совпадают => они равны } Такой алгоритм совершает в худшем случае N операций, если длина обеих строк - N символов. Оценка сложности алгоритма обозначается O(N) - это значение может быть относительно грубым и обычно рассчивается исходя "наихудшего" варианта развития событий, константные значения обычно опускаются. Оценка сложности этого алгоритма в лучшем случае - O(1) .

Кроме проверки на равенство строки можно сравнивать почти как числа - по-символьно. Встроенный метод - Compare() . Есть несколько вариантов реализации, они дают разные результаты. Один алгоритм сравнивает символы слева направо и позволяет при сортировке выстроить строки в лексикографическом порядке - т.е. алфавитном: int Compare(string a, string b) { // обычно такие функции возвращают разность (a - b) или одно из трёх значений: 1, 0, -1 int n = Math.Min(a.Length, b.Length); for (int i = 0; i < n; i++) { if (a[i] != b[i]) { if (a[i] > b[i]) { // сравнение символов производится по их коду, т.е. 'a' > 'A' return 1; } else { return -1; } } } if (a.Length > b.Length) { return 1; } else if (a.Length < b.Length) { return -1; } else { return 0; } } При такой реализации строка "2" будет больше чем "10" . Если требуется сравнивать строковые представления чисел, в алгоритме следует поставить сравнение длин строк в самое начало.

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

Встроенный метод - IndexOf . В общем случае он выполняет код, подобный следующему: int IndexOf(string what, string where) { bool flag; for (int i = 0; i < where.Length - what.Length + 1; i++) { // перебор индексов начала подстрок flag = true; for (int j = 0; j < what.Length; j++) { // перебор индексов искомой строки if (where[i + j] != what[j]) { // если хотя бы один символ не совпал с проверяемой подстрокой flag = false; break; } } if (flag) { // если все символы совпали return i; // возвращается индекс начала подстроки } } return -1; // подстрока не была найдена } Встроенный метод вызывает от самой строки "abcde".IndexOf("cd") , в которой будет производиться поиск, и может принимать различные другие аргументы, как, например, индекс, с которого следует начинать поиск или сколько символов строки стоит проверять. Сложность такого алгоритма - порядка O(N2) , если считать, что обе строки имеют длину в N символов. Точнее оценка O((N-M)M)=O(NM-M2) , если длины исходной и искомой строк N и M соответственно. Таким образом, если у вас текст из порядка 106 символов и в нём требуется найти 100 подстрок по 100 символов, такой алгоритм должен будет совершить порядка 1010 операций - для сравнения, процессор компьютера может выполнять в районе 108 простейших операций в секунду. Поэтому для решения задачи поиска в заведомо большом тексте используется другой - более сложный - алгоритм.

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

Встроенный метод - Join . В других языках он может называться implode или glue . string Implode(string glue, string[] arr) { string res = arr[0]; for (int i = 1; i < arr.Length; i++) { res += glue + arr[i]; } return res; } Этот метод перебирает все элементы массива и вставляет "строку-клей" между ними. Это бывает необходимо при более жёстких форматах вывода, когда, например, в файле после последнего элемента массива в строке не должно быть разделительного символа, а только перевод строки. В таком случае обычный подход даст немного другой результат: // StreamWriter fout = .... foreach (var item in arr) { fout.Write("{0}, ", item); // вывод будет такой: 1, 2, 3, 4, } Важно, что встроенный метод - статический и вызывается следующим образом: String.Join(separator, arr); . Так же во встроенном методе используется более оптимальный способ конкатенации строк, так как это достаточно дорогая операция: выделяется память под новый результат, все данные копируются туда, память с предыдущей строкой освобождается.

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

Встроенный метод - Split() . Реальный код метода использует другую структуру данных вместо массива. string[] Split(char separator, string arg, bool removeEmpty = false) { // флаг removeEmpty показывает, убирать пустые результаты или нет int count = 0; // чтобы создать массив для результатов, сначала необходимо посчитать их количество int subCount = 0; // счётчик символов, находящихся между разделителями - т.е. длина текущего "слова" foreach (var c in arg) { if (c == separator) { // если очередной символ - разделитель, значит мы на границе "слова", надо его посчитать if ((removeEmpty && (subCount != 0)) || !removeEmpty) { count++; } subCount = 0; } else { // иначе, надо увеличеть счётчик длины текущего "слова" subCount++; } } string[] res = new string[count]; string buffer = ""; count = 0; // теперь count отвечает за индекс "слова" в массиве результатов foreach (var c in arg) { if (c == separator) { if ((removeEmpty && (buffer.Length != 0)) || !removeEmpty) { res[count] = buffer; count++; buferr = ""; } } else { buffer += c; // вместо счётчика теперь символы "слова" добавляют в буферную строку } } return res; } Этот метод несколько усложняется, если в качестве разделителя должен выступать не один символ, а целая строка.