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

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 に答える
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 に答える