Контекстная замена

Контекстная замена -поиск и замена в строке фрагментов, заданных одной строкой (контекста) на фрагмент, заданный другой, например:

Исходная строка Заменяемая Заменяющая Результат

строка строка

"abc234pe4234e" "234" "_00_" "abc_00_pe4_00_e"

Особенность программы: обработка строки производится не путем ее переписывания, а с помощью сдвига “хвоста” строки вправо или влево. Ввиду сложности алгоритма приведем его в пошаговой детализации.

Шаг 1: Исходные данные и результат. Строки заданы массивами символов s,s1,s2. Результирующая строка размещается в том же массиве, что и исходная. Контроль размерности не производится:

void Context(char s[], char s1[], char s2[]) {...}

Шаг 2: Основной цикл программы состоит в посимвольной проверке строки на вхождение в нее подстроки, начиная с текущего символа. В случае вхождения производится замена:

void Context(char s[], char s1[], char s2[])

{

int n;

for (n=0; s[n]!='\0'; n++)

{

// Если начиная с n-го символа расположена

// подстрока s1, заменить ее на s2 в строке

}

}

Шаг 3: Проверка утверждения, что начиная с n-го символа в строке s расположена подстрока s2:

int i;

for (i=0; s[n+i]!='\0' && s1[i]!='\0'; i++)

if (s[n+i]!= s1[i]) break;

if (s1[n+i]=='\0')

{

// заменить s1 на s2 в строке, начиная с s[n]

}

Шаг 4: Замена подстроки s1 на s2, начиная с n-го символа строки s, заключается перемещении "хвоста" строки s вправо или влево в зависимости от знака разности длин строк и в переписывании строки s2 на место строки s1. Для получения длины строки воспользуемся стандартной функцией strlen:

int l2,dd,k;

l2 = strlen(s2)

dd = l2 - strlen(s1);

if (dd!= 0)

{

// сдвинуть "хвост" строки s на dd символов

}

for (k = 0; k < l2; k++)

s[n+k] = s2[k];

Шаг 5: Для сдвига всего "хвоста" (для простоты, начиная с n-го символа) влево (dd < 0) необходимо все символы, начиная с n+dd перенести на dd позиций влево. Для перемещения вправо нужно сначала найти конец строки, чтобы от него производить перемещения символов с убывающим индексом

if (dd < 0)

{

for (k=n; s[k+dd]!='\0'; k++)

s[k] = s[k+dd];

s[k]='\0';

}

else

{

for (k=n; s[k]!='\0'; k++);

for (; k!= n; k--)

s[k+dd] = s[k];

}

Примечание: в случае удачной замены проверка возможности последующей замены производится, начиная со следующего символа. Тогда при наличии замен вида "nnn" на "nnnn..." программа будет расширять строку до бесконечности.