Алгоритмы на строках

Пример 1. Найти сумму всех цифр, входящих в строку s.

if s[i] in ['0'..'9'] then   sum:=sum+(Ord(s[i]-Ord('0'));

Пример 2. Найти последнее вхождение подстроки s1 в строку s.

Решение. Инвертировать обе строки, найти первое вхождение и скорректировать его.

s1:='efg'; s:='efgabcdefgh'; Invert(s); // сами пишем Invert(s1); // сами пишем i:=Pos(s1,s); i:=Length(s)-i+1-Length(s1)+1;

Пример 3. Удаление лишних пробелов в строке.

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

procedure DeleteSpaces(const s: string; var s1: string); var   i,j: integer; // j - текущий индекс второй строки   f: boolean; // f=True - предыдущий символ является пробелом begin   s1:='';   f:=True;   j:=0;   for i:=1 to Length(s) do   begin     if not f or (s[i]<>' ') then // если предыдущий - не пробел или текущий - не пробел     begin       Inc(j);       s1[j]:=s[i];     end;     f:=s[i]=' '; // f=True - предыдущий символ является пробелом   end;   if s1[j]=' ' then // Если последний - пробел, то удалить     Dec(j);   SetLength(s1,j); end;

Решение 2. Второй вариант решения - с использованием стандартных функций.

procedure DeleteSpaces1(const s: string; var s1: string); var p: integer; begin   s1:=s;   if s1='' then Exit;   p:=Pos('  ',s1);   while p<>0 do // пока есть два подряд идущих пробела   begin     Delete(s1,p,1); // первый из них удалять     p:=Pos('  ',s1);   end;   if s1[1]=' ' then // Если первый - пробел, то удалить     Delete(s1,1,1);   if s1='' then Exit;   if s1[Length(s1)]=' ' then // Если последний - пробел, то удалить     Delete(s1,Length(s1),1); end;

Пример 4. Разбиение строки слов на отдельные слова.

Решение 1.

type SArr=array [1..100] of string;

procedure Split(const s: string; var a: SArr; var n: integer); var i,j,l: integer;

 procedure PassSpaces;  begin    while (i<=l) and (s[i]=' ') do      Inc(i);  end;

 procedure PassNonSpaces;  begin     while (i<=l) and (s[i]<>' ') do       Inc(i);  end;

begin   n:=0; // количество слов   i:=1;   l:=Length(s);   PassSpaces;   while i<=l do   begin     j:=i; // индекс первого непробела     PassNonSpaces;     Inc(n);     a[n]:=Copy(s,j,i-j);     PassSpaces;   end; end;

Решение 2. Обобщение на произвольные разделители между словами.

type Charset = set of char;

procedure Split(const s: string; var a: SArr; var n: integer; Delimiters: Charset=[' ']); var i,j,l: integer;

procedure PassSpaces; begin   while (i<=l) and (s[i] in Delimitres) do     Inc(i); end;

procedure PassNonSpaces; begin   while (i<=l) and not (s[i] in Delimitres) do     Inc(i); end;

begin   n:=0;   i:=1;   l:=Length(s);   PassSpaces;   while i<=l do   begin     j:=i;     PassNonSpaces;     Inc(n);     a[n]:=Copy(s,j,i-j);     PassSpaces;   end; end;

Использование Split

Удаление лишних пробелов - способ 3.

procedure Merge(const a: SArr; n: integer; var s: string); begin   s:='';   for i:=1 to n-1 do     s:=s+a[i]+' ';   s:=s+a[n]; end; ... Split(s,a,n); Merge(a,n,s); // объединение в строку s всех слов массива а

Пример 5. Отсортировать слова в строке s по алфавиту, удалив лишние пробелы.

Решение.

Split(s,a,n); BubbleSort(a,n); Merge(a,n,s);

Пример 6. Составить частотный словарь слов, встречающихся в строке.

Решение.

type   FregNote = record // Запись в частотном словаре     word: string;   // слово     count: integer; // количество   end;

FreqDic: array [1..Dim] of FreqNote; // Частотный словарь

function IndexOf(s: string; const b: FreqDic; m: integer): integer; begin   // написать самостоятельно end;

procedure AddToFregDic(s: string; var b: FreqDic; var m: integer); begin   i:=IndexOf(s,b,m); // индекс строки в частотном словаре   if i:=0 then // если не найдена   begin     Inc(m);     b[m].word:=s;  // то добавить в конец     b[m].count:=1; // и установить счетчик слов равным 1   end   else Inc(b[i].count); // иначе увеличить счетчик данного слова end;

Split(s,a,n); for i:=1 to n do   AddToFregDic(s,b,m); SortFreqDicByWords(b,m); // SortFreqDicByWords написать самостоятельно WriteFregDic(b,m); // WriteFregDic написать самостоятельно