Строки как тип информации очевидно появились в компьютерных задачах обработки текстов, причем среди таких текстов очень быстро появились компьютерные программы — тексты, написанные на специально созданном алгоритмическом языке. Формальный анализ текстов на таком языке значительно легче, чем на естественном. Но были и такие задачи, где вынужденно использовался естественный язык — его специально упрощали.

По мере того, как накапливались стандартные методы представления строковой информации и операции над ней, выяснялось, что объекты типа строк уже используются или должны использоваться во многих математических моделях.

Особо нужно упомянуть о математической генетике, где строка — одно из самых важных понятий.

В этой лекции мы формально определим, что такое строка, рассмотрим наиболее характерные действия со строками, а затем перечислим некоторые приложения строк.

Психологически удобно иметь в качестве основного примера строку текста, и подготовка к определениям начинается с фразы:

Пусть задано конечное множество  A,  которое будет называться алфавитом, а его элементы буквами. Обычно сразу же требуется, чтобы на  A  было задано упорядочение, что эквивалентно требованию нумерации букв. На самом деле, нумерация в реально используемых алфавитах может легко изменяться в зависимости от поставленной задачи.

Строки — это произвольные последовательности, составленные из букв, причем любая буква может встречаться в последовательности любое число раз. Например, вот несколько строк над алфавитом строчных русских букв:

      аааааааахахахааааа
      пришелувиделпобедил
      эта строка незаконная

Действительно, последний пример ошибочен. Почему?

Количество букв в строке называется ее длиной. Строка нулевой длины называется пустой строкой.

Обычно рассматриваются строки, длина которых заранее не фиксируется, этим строки отличаются от векторов в математике и массивов в программировании. Они очень похожи на последовательности. Д. Гасфилд, автор очень интересной книги о задачах, связанных со строками, отметил одно единственное различие между строками и последовательностями: производные от них понятия подстроки и подпоследовательности обозначают разное. Подстрока — это подпоследовательность, составленная из букв строки, идущих подряд. Таким образом, в строке

      пришелувиделпобедил

есть подстрока обед и нет подстроки депо.

Подстроку легко задать, указав ее позицию начальной буквы и длину (для подстроки обед это (14,4), если символы нумеруются от 1, и (13,4) при нумерации от 0).

Подстрока, у которой начальная позиция совпадает с начальной позицией самой строки, называется префиксом строки, а подстрока, у которой конечная позиция совпадает с конечной позицией самой строки, называется суффиксом строки. Префиксы нам уже встречались при определении префиксных кодов. Сами эти кодовые комбинации были строкам над алфавитом 0:1.

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

В языке Паскаль есть специальный тип данных string, и мы можем описать новую строку, переменную или константу, и выполнить с нею предусмотренные действия, в том числе и такие, которые изменяют длину строки. При этом изменении строка может передвинуться с одного места в памяти на другое, само перемещение выполняет система поддержки, и программисту не нужно о нем беспокоиться.

В тексте программы переменные строки описываются очень просто:

sName: string;

Строковые константы заключаются в апострофы:

const
    sOrg = 'матмех СПбГУ';

В исполняемой программе строка хранится в виде байтового массива, причем недоступный программисту начальный, нулевой, байт содержит длину самой строки.

В языке Си строки рассматриваются как последовательности байтов, записанных подряд. Строка заканчивается байтом с нулевым значением, поэтому байты с нулевым значением внутри строки не разрешены. Такой формат принято называть ASCIIZ (ASCII + Zero). Размещение строки в памяти оставляется на усмотрение самого програм­миста. В этом языке вычисление длины строки — это именно вычисление. Впрочем, в системе команд процессоров персональных компьютеров уже давно есть команда просмотра памяти до нахождения байта с нужным значением, так что функция, вычисляющая длину строки работает очень быстро.

В языке С++ тип строка уже есть, размещением строки занимается система.

Перечислим те операции, которые мы уже рассмотрели, и добавим некоторые новые.

1. Вычисление длины строки.
   
   
2. Выделение подстроки (префикса, суффикса, произвольного фрагмента).
   
   
3. Инвертирование строки. Эта операция с текстовыми строками используется редко, а в числовых строках встречается.
   
   
4. Конкатенация строк — соединение нескольких подряд расположенных строк в одну. Иногда говорят катенация строк. Слово происходит от латинского catena — цепь. Так что слово сцепление тоже вполне бы подошло.
   
   
5. Сравнение строк. Часто на множестве строк нужно ввести упорядочение. Обычно оно определяется упорядочением букв алфавита и называется лексикографическим. Оно нам уже встречалось, но придется обсудить кое-что еще.
   
   
6. Поиск образца. Очень важная операция. Есть две строки: длинная T — текст и короткая P — образец (от Text и Pattern). Нужно найти в строке-тексте подстроки, совпадающие с образцом. Это очень важная операция, о ней мы будем говорить отдельно.
   
   
7. Подстановка — фрагмент строки заменяется чем-то другим. Эта операция включает в себя предыдущую.
   
   
8. Поиск максимального совпадения двух строк. Рассмотрим отдельно.
   
   
9. Нахождение редакционного расстояния. Рассмотрим отдельно.

А теперь рассмотрим подробно те операции, о которых мы раньше не говорили или говорили недостаточно.

Наиболее распространено уже неоднократно встречавшееся нам лексикографическое сравнение строк, которое основывается на упорядочении букв алфавита, из которых формируются эти строки. Если сравнивать буквы по кодам ASCII (и так обычно и делается), то эффект может быть не очень приятным для нас. Часто мы можем видеть. что получается в алфавитных указателях современных книг: даже в русскоязычных книгах кириллица следует за латиницей, а перед латиницей расположены всевозможные служебные символы. Например, получится такой порядок «слов» (столбец за столбцом)

!24	1	@ma.ru	brot	АЛГОЛ
#no	115	Bern	{1,3}	Автор
$2445	2	Moscow	~exe	Кнут
&my;	201	ZZW	€73	буква
(about)	21	Ziv	—	знание
+44-15	7	[15]	Ёлка	шар
/log	73	big	№45	шушера

Такой порядок, без сомнения, будет для нас неприятен.

А чего же мы хотели бы?

Лучше всего, если бы сначала шла кириллица, причем без разделения прописных и строчных букв, а специальные знаки могут и пропускаться, затем так же латиница, затем числа, затем в каком-нибуль порядке все знаки. Чтобы получилось как-нибудь так

Автор	шушера	@ma.ru	115	$2445
АЛГОЛ	(about)	Moscow	[15]	+44-15
буква	Bern	&my;	{1,3}	№45
Ёлка	big	#no	2	7
знание	brot	Ziv	201	73
Кнут	~exe	ZZW	21	€73
шар	/log	1	!24	—

Многие простые модификации упорядочения можно выполнить единообразно, если сопоставить всем буквам алфавита числа, задающие их ранг в упорядочении. Например, всем буквам русского языка сопоставить номера идущие подряд, одинаковые для прописных и строчных букв.

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

9

ђ

‘

’

“

”

•

–

—

undef

™

љ

›

њ

ќ

ћ

џ

A

nbsp

Ў

ў

Ј

d

Ґ

¦

§

Ё:7

©

Є

«

¬

shy

®

Ї

B

°

±

І

і

ґ

µ

¶

·

ё:7

№

є

»

ј

Ѕ

ѕ

ї

C

А:1

Б:2

В:3

Г:4

Д:5

Е:6

Ж:8

З:9

И:10

Й:11

К:12

Л:13

М:14

Н:15

О:16

П:17

D

Р:18

С:19

Т:20

У:21

Ф:22

Х:23

Ц:24

Ч:25

Ш:26

Щ:27

Ъ:28

Ы:29

Ь:30

Э:31

Ю:32

Я:33

E

а:1

б:2

в:3

г:4

д:5

е:6

ж:8

з:9

и:10

й:11

к:12

л:13

м:14

н:15

о:16

п:17

F

р:18

с:19

т:20

у:21

ф:22

х:23

ц:24

ч:25

ш:26

щ:27

ъ:28

ы:29

ь:30

э:31

ю:32

я:33

Мы пишем в ячейках таблицы и буквы и их номера, там где они есть, чтобы было виднее. Обратите внимание на скачок нумерации в строке B: он связан с необходимостью вставить в общий порядок букву Ё, которая не включена в стандартный порядок основных 32 букв. Для учета особенностей украинского алфавита (кулишивка) аналогичные скачки пришлось бы сделать для букв Ґ, Є, І и Ї и для удаления букв кириллицы, не входящих в кулишивку.

Дальше можно аналогично расположить латиницу (опустим для простоты нумерацию строчных букв), а затем и цифры

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

3

0:60

1:61

2:62

3:63

4:64

5:65

6:66

7:67

8:68

9:69

:

;

<

=

>

?

4

@

A:34

B:35

C:36

D:37

E:38

F:39

G:40

H:41

I:42

J:43

K:44

L:45

M:46

N:47

O:48

5

P:49

Q:50

R:51

S:52

T:53

U:54

V:55

W:56

X:57

Y:58

Z:59

[

\

]

^

_

После этого можно в желательном порядке расположить прочие знаки. Построенная таким образом таблица (очень скромного размера — 256 байтов) может использоваться в функции сравнения символов. Надо сравнивать не сами символы, а их ранги. Можно еще выделить особо нулевой ранг, делая символы с нулевым рангом невидимыми для сортировки.

Но конечно, этим усовершенствованием все проблемы не решаются. Например, часто неудобно лексикографическое сравнение строк, в которых содержатся числа. Если в телефонном справочнике строка "Школа 239" предшествует строке "Школа 45", а "аптека 4" стоит за "аптека 141", это может вызвать большие неудобства: человек ищет школы и аптеки по порядку номеров и может просто не найти нужный телефон. Мне, хотя я и знаю этот эффект, часто приходится страдать от него при поиске нужных файлов — как правило, они упорядочиваются лексикографически. Единственный известный мне пример учета чисел в строках — это программа Photoshop.

Сейчас мы рассмотрим одну экстремальную задачу, связанную со строками.

Пусть задан алфавит  A  и две строки над этим алфавитом  a  длины  kA  и  b  длины  kB.  Требуется найти в этих строках монотонно возрастающие подпоследовательности совпадающих символов (следовательно, длина у этих подпоследовательностей должна быть одной и той же), имеющие наибольшую длину.

Обозначим через  k  длину искомых подпоследовательностей, а через  i₁, i₂, ... i_k  и  j₁, j₂, ... j_k  сами эти подпоследовательности.

Сейчас мы рассмотрим очень важный метод решения этой задачи, который называется методом динамического программирования. Динамическое программирование было придумано американским математиком Ричардом Беллманом.

Идея метода состоит в том, что решение нужной нам задачи заменяется решением большого числа однотипных задач, которые решаются вместе, а в таком коллективном решении каждая задача использует результаты решения других задач. Посмотрим, как это выглядит в нашем случае.

Обозначим искомую максимальную длину совпадающих подпоследовательностей через  ν(kA,kB),  таким обозначением мы намекаем на то, что будут решаться и другие задачи, для любых префиксов строк  a  и  b.  Итак,  ν(iA,iB),  — это максимальная длина совпадающих подпоследовательностей в  a[1:iA]  и  b[1:iB]. 

Теперь мы можем убедиться в том, что легко составить таблицу значений этой функции, обозначим ее через
 v[1:kA,1:kB]. 

Начнем с простейшего. Обозначим через  δ(i,j)  функцию, равную 1 при  a[i] = b[j]  и 0 в противном случае. Тогда, очевидно,  v[1,1] = δ(1,1).  Далее, можно было бы сказать, что при  k > 1  значение  v[1,k] = 1,  в том и только том случае, когда в строке  b[1:k]  присутствует символ  a[1]. 

Но правильнее будет убедиться в справедливости соотношения
    v[1,k] =  max { v[1,k−1], δ(1,k) }. 
Это соотношение освободит нас от обязанности искать каждый раз заново символ  a[1]  в строке  b[1:k].

Самое же главное то, что это соотношение побуждает нас искать аналогичное и для произвольного элемента таблицы с индексами  i  и  k.  Если  a[i] = b[k],  то совпадение последних символов нужно использовать и перейти к меньшим строкам
    v[i,k] =  1 + v[i−1,k−1]. 
В противном случае, мы только выбираем, от какого из двух последних символов должны освободиться, и переходим к одной из двух меньших задач
    v[i,k] =  max{v[i,k−1], v[i−1,k]. 

Полученное соотношение можно использовать для очень простого вычисления всей таблицы, например, по строчкам, от меньших значений индексов к большим.

Например, при сопоставлении строк
      bambambambam
и
      maambamaamba
мы построим такую таблицу 12×12.
        bambambambam
      m 001111111111
      a 011122222222
      a 011122233333
      m 012223334444
      b 112333444555
      a 122344455566
      m 123345556667
      a 123345566677
      a 123345566677
      m 123345567778
      b 123445667888
      a 123455677899

После того, как построена эта таблица, можно по ней найти и максимальную общую подпоследовательность. Соответствующие ей символы выделены на таблице красным цветом.