Информатика и технология программирования

       

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


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


Исходная строка Заменяемая Заменяющая Результат
строка строка
"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' &#38&#38 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 &#60 l2; k++)
s[n+k] = s2[k];

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


if (dd &#60 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..." программа будет расширять строку до бесконечности.



Содержание раздела