Замена рисунка в строке на месте

Question

В одном из интервью мне был задан вопрос о строках. Задача задается строкой s1 = "ABCDBCCDABCD". и шаблон "BC". мы должны заменить этот шаблон другой строкой ("UVW" или "U" или "uv"). Это должно быть на месте.

    Take the case as:  
          replace "BC" with  following 
 a) "uvw"   s1=AUVWDUVWCDAUVWD .
 b)  "U"    s1=AUDUCDAUD .
 c)  "UV"   s1=AUVDUVCDAUVD .

Будет полезно, если кто-то предоставит программу вместе с алгоритмом.

Answer 1

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

Создайте переменную для хранения текущего индекса в шаблоне.

Цикл по входной строке, если текущий символ соответствует символу в индексе в шаблоне, то мы увеличиваем индекс.

Если индекс теперь равен длине шаблона, добавьте строку замены к выводу и сбросьте индекс

Если текущий символ не совпадает с символом в индексе в шаблоне, тогда добавьте все от шаблона до (и включая) индекс в шаблоне и сбросьте индекс.

В Ja va это выглядит примерно так:

public static void main(String[] args) {
    final String s = "ABCDBCCDABCD";
    System.out.println(replaceAll(s, "BC", "UVW"));
    System.out.println(replaceAll(s, "BC", "U"));
    System.out.println(replaceAll(s, "BC", "UV"));
}

public static String replaceAll(final String in, final String p, final String r) {
    final List<Character> newString = new LinkedList<>();

    final List<Character> pattern = new ArrayList<>();
    for (final Character c : p.toCharArray()) {
        pattern.add(c);
    }
    final List<Character> replace = new ArrayList<>();
    for (final Character c : r.toCharArray()) {
        replace.add(c);
    }
    int positionInPattern = 0;
    for (final char c : in.toCharArray()) {
        if (c == pattern.get(positionInPattern)) {
            positionInPattern++;
            if (positionInPattern == pattern.size()) {
                newString.addAll(replace);
                positionInPattern = 0;
            }
        } else {
            if (positionInPattern > 0) {
                newString.addAll(pattern.subList(0, positionInPattern + 1));
                positionInPattern = 0;
            }
            newString.add(c);
        }
    }
    final StringBuilder sb = new StringBuilder();
    for (final Character c : newString) {
        sb.append(c);
    }
    return sb.toString();
}

Выход:

AUVWDUVWCDAUVWD
AUDUCDAUD
AUVDUVCDAUVD

Answer 2

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

Если замещающая строка длиннее исходного шаблона, мы сначала сканируем шаблон и вычисляем длину новой строки. Затем мы вызываем realloc, чтобы расширить доступный буфер и начать копирование в строку назад.

[A][B][C][D][B][C][C][D][A][B][C][D][␀]
# extend buffer:
[A][B][C][D][B][C][C][D][A][B][C][D][␀][ ][ ][ ]
# after first few iterations of the copy loop
[A][B][C][D][B][C][C][D][A][B][C][D][␀][ ][ ][␀]
[A][B][C][D][B][C][C][D][A][B][C][D][␀][ ][D][␀]
[A][B][C][D][B][C][C][D][A][B][C][D][␀][C][D][␀]
[A][B][C][D][B][C][C][D][A][B][C][U][V][W][D][␀]
[A][B][C][D][B][C][C][D][A][B][A][U][V][W][D][␀]

Мой C немного ржавый, но этот код, похоже, выполняет свою работу:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int pat_match(char* str, char* pattern)
{
    while(*pattern == *str) 
    {
        if(*pattern == '\0' || *str == '\0') break;
        pattern++;
        str++;
    }
    return (*pattern == '\0');
}

char* replace(char* str, char* pattern, char* rep)
{
    int len_str = strlen(str);
    int len_pattern = strlen(pattern);
    int len_rep = strlen(rep);

    if(len_rep > len_pattern)
    {
        int count_matches = 0;
        char* scan = str;
        while(*scan) 
        {
            if(pat_match(scan, pattern))
            {
                printf("Match!\n");
                count_matches++;
                scan += len_pattern;
            }
            else
            {
                scan++;
            }
        }
        if(count_matches == 0) return str;

        int len_new = len_str + count_matches * (len_rep - len_pattern);

        str = realloc(str, len_new+1);
        int new_pos, pos;
        for(pos=len_str-1,new_pos=len_new-1;pos>=0;pos--,new_pos--)
        {
            if(pat_match(str+pos, pattern))
            {
                memcpy(str+new_pos-(len_rep-len_pattern), rep, len_rep);
                new_pos = new_pos - (len_rep-len_pattern);
            }
            else
            {
                str[new_pos] = str[pos];
            }
        }
        str[len_new] = '\0';
    }
    else
    {
        int new_pos, pos;
        for(pos=0,new_pos=0; pos<len_str; pos++,new_pos++)
        {
            if(pat_match(str+pos, pattern))
            {
                memcpy(str+new_pos, rep, len_rep);
                pos += len_pattern-1;
                new_pos += len_rep-1;
            }
            else
            {
                str[new_pos] = str[pos];
            }
        }
        str[new_pos] = '\0';
    }

    return str;
}

void main() 
{
    char* s = (char*)malloc(12);
    strcpy(s, "Hello world");
    printf("%s\n", replace(s, "llo", "x"));
}