5.Обработка текста

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

const n = 5000;

Var T: array [1..n] of char;

Текст в массив T заносится путем ввода или присваивания элементам массива T[1], T[2] и т.д. значений отдельных символов. Для удобства работы с текстом в программе желательно описать переменную, которая будет содержать текущую длину текста, например:

Var L: integer;

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

Когда в задаче нужно работать с отдельными словами, то удобнее использовать строковые переменные или массивы строк. В этом случае описание строк символов может быть, например, следующим:

const dl = 100;

m = 50;

Var S1, S2, S3: string[dl];

Slova:array[1..m]of string[dl];

Текст заносится в строку путем присваивания всей строке подходящего значения (которое в данном примере не должно быть длиннее, чем dl), или оператором ввода с клавиатуры, например:

S1:=’Петя’; S2:=’Вася’; Readln(S3);

Текущую длину текста в строке всегда можно вычислить функцией Length. Например, после присваивания i:=Length(S1) величина i = 4. Кроме того, можно склеивать строки операцией «+», например:

S3:=S1+’ ’+S2; i:=Length(S3);

{Результат: S3=’Петя Вася’, i = 9}

Доступ к отдельным символам в массиве или в строке (т.е. в обоих случаях) выполняется путем указания номера этого символа, т.е. с помощью индекса, например: T[1], S1[i]. Отдельные символы можно сравнивать между собой (операциями «=», «<>», «<», «<=» и т.п.). При этом следует иметь в виду, что строчные буквы упорядочены между собой в алфавитном порядке: ’а’<’б’< ... <’я’. Аналогично упорядочены и заглавные буквы: ’А’<’Б’< ... <’Я’. Между тем сравнение строчных букв с заглавными некорректно. Строки символов также можно сравнивать, при этом выполняется лексикографическое сравнение, такое же, как при размещении слов по алфавиту (но только отдельно для строчных букв и отдельно для заглавных!).

Рассмотрим ряд типовых примеров.

Поиск подстроки в тексте. Задан текст T и подстрока S. Найти эту подстроку в тексте, т.е. определить тот номер символа i, начиная с которого S размещается в тексте T.

Алгоритм, решающий эту задачу, в цикле отыскивает символ в тексте, совпадающий с 1-м символом подстроки. Как только такое совпадение обнаружится, проверяются совпадения последующих символов подстроки и текста.

Const n=250;

dl=50;

Var T:string[n]; {Переменная для текста}

S:string[dl]; {Переменная для подстроки}

i,j,nt,ns:integer;

begin Readln(T); {Ввод текста длиной не более, чем 250 символов}

Readln(S); {Ввод подстроки длиной не более, чем 30 символов}

nt:=Length(T); {Вычисление длины текста}

ns:=Length(S); {Вычисление длины подстроки}

for i:=1 to nt-ns+1 do

{nt-ns+1 – последняя позиция в тексте, с которой может начинаться подстрока}

if T[i]=S[1] then

begin j:=2;{проверка совпадения остальных символов подстроки с текстом}

while (j<=ns)and(T[i+j-1]=S[j]) do

j:=j+1;

{По окончании цикла j=ns+1 только в том случае, если было полное совпадение.}

if j=ns+1 then Writeln(i);

{Вывод номера символа, где начинается подстрока в тексте}

end

end.

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

Трудоемкость алгоритма. В наихудшем случае внутренний цикл выполняется ns раз для каждого фиксированного i. так как во внешнем цикле i изменяется от 1 почти до длины текста nt общая трудоемкость будет порядка nt * ns.

Поиск всех слов, имеющихся в английском тексте. Задан текст T, в котором записаны предложения на английском языке. Найти и вывести в этом тексте все слова.

Алгоритм, решающий эту задачу, в цикле отыскивает символ в тексте, являющийся буквой. Как только такой символ обнаружится, последовательно формируется слово из букв в виде строки символов. Дальнейший поиск начала нового слова производится с символа, расположенного в тексте после обнаруженного слова.

const n=251;

dl=30;

var T: string[n]; {Переменная для текста}

S: string[dl]; {Переменная для слова}

i, nt: integer;

begin Readln(T);

nt:=Length(T); {Вычисление длины текста}

T:=T+’ ’; {Добавление пробела в конце текста, чтобы текст никогда не заканчивался буквой}

i:=1;

while i<=nt do

if ((T[i]>=’A’)and(T[i]<=’Z’))or

((T[i]>=’a’)and(T[i]<=’z’)) then

{Если найдена буква после не буквенного символа в тексте}

begin S:=T[i]; i:=i+1;

while ((T[i]>=’A’)and(T[i]<=’Z’))or

((T[i]>=’a’)and(T[i]<=’z’)) do

begin S:=S+T[i]; i:=i+1; end;

{Поиск конца слова в тексте по символу «не буква» и «накапливание» слова в строке S. Когда этот (второй) цикл закончится, i будет таким, что T[i] – не буквенный символ.}

Writeln(S); {Вывод накопленного слова}

end

else i:=i+1; {Переход к следующему символу T[i]}

end.

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

Обработка слова в тексте. Дан текст T, размещенный в массиве символов. Составить алгоритм, позволяющий выполнять исследование каждого отдельного слова.

Пошаговая разработка

начальные значения;

while не кончился текст do begin

пропустить разделители;

пройти по не разделителям;

слово – в строку;

обработка слова

end;

начальные значения

i:=1; {номер символа в тексте}

не кончился текст

i<=n

пропустить разделители

while(i<=n)and

((T[i]=’ ’)or(T[i]=’.’)or(T[i]=’,’)) do

i:=i+1;

Цикл закончится либо потому, что закончился текст, либо потому, что на i-м месте встретилась буква. Это начало слова.

nach:=i;

пройти по не разделителям

while(i<=n)and

(T[i]<>’ ’)and(T[i]<>’.’)and(T[i]<>’,’) do

i:=i+1;

Цикл закончится либо потому, что закончился текст, либо потому, что на i-м месте встретился разделитель. Конец слова перед ним.

kon:=i-1;

слово – в строку

stroka:=’’;

for k:=nach to kon do

stroka:=stroka+T[k];

Возможен и другой вариант переписывания.

stroka:=’’;

for k:= kon downto nach do

stroka:=T[k]+stroka;

Количество разделителей можно увеличить.

Трудоемкость алгоритма выделения всех слов в тексте – линейная, так как работа всех циклов управляется единственной переменной i, изменяющейся от 1 до длины текста. Эта переменная при каждом выполнении любого внутреннего цикла увеличивается на 1.