3

在一次采访中，我被问到一个关于字符串的问题。问题给出了一个字符串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 .

有人提供程序和算法将对您有所帮助。

4

2 回答 2

0

我的计划是创建一个链接列表来保存最终输出。

创建一个变量来保存模式中的当前索引。

循环输入字符串，如果当前字符与模式中索引处的字符匹配，则我们增加索引。

如果索引现在等于模式的长度，则将替换字符串附加到输出并重置索引

如果当前字符与模式中索引处的字符不匹配，则将模式中的所有内容附加到（并包括）模式中的索引并重置索引。

在 java 中，这看起来像：

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
于 2013-03-23T14:23:13.847 回答
0

实际上，您可以在具有 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"));
}
于 2014-07-15T13:55:02.037 回答