Folgeersetzung

30

Die meisten Sprachen verfügen über eine integrierte Funktion, mit der eine Zeichenfolge nach allen Vorkommen einer bestimmten Teilzeichenfolge durchsucht und durch eine andere ersetzt werden kann. Ich kenne keine Sprache, die diesen Begriff auf (nicht unbedingt zusammenhängende) Teilfolgen verallgemeinert. Das ist also Ihre Aufgabe bei dieser Herausforderung.

Die Eingabe besteht aus drei Zeichenfolgen A, Bund C, wo Bund Csind garantiert gleich lang. Wenn dies Bals Folge erscheint A, sollte es durch ersetzt werden C. Hier ist ein einfaches Beispiel:

A: abcdefghijklmnopqrstuvwxyz
B: ghost
C: 12345

Es würde so verarbeitet werden:

abcdefghijklmnopqrstuvwxyz
      ||      |   ||
abcdef12ijklmn3pqr45uvwxyz

Wenn es mehrere Möglichkeiten gibt, Beine Unterfolge zu finden , sollten Sie die ganz linke gierig ersetzen:

A: abcdeedcba
B: ada
C: BOB

Result:   BbcOeedcbB
and NOT:  BbcdeeOcbB

Das gleiche gilt, wenn Ban mehreren getrennten Orten gefunden werden könnte:

A: abcdeedcbaabcde
B: ed
C: 12

Result:   abcd1e2cbaabcde
and NOT:  abcd112cbaabc2e (or similar)

Wenn in Bnicht angezeigt wird A, sollten Sie Aunverändert ausgeben .

Regeln

Wie oben erwähnt, nehmen drei Saiten A, Bund Cals Eingabe und ersetzen Sie die am weitesten links Auftreten Bals Teilfolge in Amit C, wenn es irgendwelche gibt.

Sie können ein Programm oder eine Funktion schreiben, indem Sie eine Eingabe über STDIN (oder die nächstgelegene Alternative), ein Befehlszeilenargument oder ein Funktionsargument vornehmen und das Ergebnis über STDOUT (oder die nächstgelegene Alternative), einen Funktionsrückgabewert oder einen Funktionsparameter (out) ausgeben.

Sie können die drei Zeichenfolgen in beliebiger Reihenfolge verwenden, die Sie in Ihrer Antwort angeben sollten. Sie können das annehmen Bund Chaben die gleiche Länge. Alle Zeichenfolgen enthalten nur alphanumerische Zeichen.

Es gelten die Standardregeln für .

Testfälle

Jeder Testfall ist vier Zeilen: A, B, Cdurch das Ergebnis gefolgt.

abcdefghijklmnopqrstuvwxyz
ghost
12345
abcdef12ijklmn3pqr45uvwxyz

abcdeedcba
ada
BOB
BbcOeedcbB

abcdeedcbaabcde
ed
12
abcd1e2cbaabcde

121
121
aBc
aBc

abcde
acb
123
abcde

ABC
ABCD
1234
ABC

012345678901234567890123456789
42
TT
0123T5678901T34567890123456789

edcbaedcbaedcbaedcba
abcde
12345
edcbaedcbaedcbaedcba

edcbaedcbaedcbaedcbaedcba
abcde
12345
edcb1edc2aed3bae4cba5dcba

daccdedca
ace
cra
dcrcdadca

aacbcbabcccaabcbabcaabbbbca
abaaaccbac
1223334444
aacbcbabcccaabcbabcaabbbbca

aacbcbabcccaabcbabcaabbbbcac
abaaaccbac
1223334444
1ac2cb2bccc33b3bab4aa4bbbc44

Bestenliste

Das Stapel-Snippet am Ende dieses Beitrags generiert Ranglisten aus den Antworten a) als Liste der kürzesten Lösungen pro Sprache und b) als Gesamtrangliste.

Um sicherzustellen, dass Ihre Antwort angezeigt wird, beginnen Sie Ihre Antwort mit einer Überschrift. Verwenden Sie dazu die folgende Markdown-Vorlage:

## Language Name, N bytes

Wo Nist die Größe Ihres Beitrags? Wenn Sie Ihren Score zu verbessern, Sie können alte Rechnungen in der Überschrift halten, indem man sich durch das Anschlagen. Zum Beispiel:

## Ruby, <s>104</s> <s>101</s> 96 bytes

Wenn Sie mehrere Zahlen in Ihre Kopfzeile aufnehmen möchten (z. B. weil Ihre Punktzahl die Summe von zwei Dateien ist oder wenn Sie die Strafen für Interpreter-Flags separat auflisten möchten), stellen Sie sicher, dass die tatsächliche Punktzahl die letzte Zahl in der Kopfzeile ist:

## Perl, 43 + 2 (-p flag) = 45 bytes

Sie können den Namen der Sprache auch als Link festlegen, der dann im Snippet angezeigt wird:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

Martin Ender
quelle
Wäre eine Liste einzelner Zeichenfolgen für die Eingabe / Ausgabe in Ordnung?
FryAmTheEggman
@FryAmTheEggman Hm, der einzige Konsens ich finden kann , ist dies nicht Listen von Einzelzeichenketten als gültige Zeichenfolge Darstellungen nicht ansprechen. Es könnte sich lohnen, einen Metapost zu verfassen (vor allem, weil ich denke, dass dies auch bei der neuesten Herausforderung von xnor der Fall war). Ich werde jetzt nein sagen.
Martin Ender
Was ist mit Zeichenarrays? Dies scheint zu implizieren, dass sie zulässig sind, auch wenn die Sprache einen geeigneten Zeichenfolgentyp hat.
Dennis
@Dennis Ja, Zeichen-Arrays sind in Ordnung, aber Singleton-Strings sind so, als würde man ein Array von ganzen Zahlen als nehmen [[1], [2], [3]].
Martin Ender
OK, danke, dass du das geklärt hast.
Dennis

Antworten:

3

Jelly , 23 22 21 Bytes

='T€ŒpfṢ€$ḢṬœp³ż⁵$³Ḋ?

Probieren Sie es online! Beachten Sie, dass den letzten beiden Testfällen der Speicherplatz ausgeht.

Nachprüfung

$ head -n 5 test-cases
abcdefghijklmnopqrstuvwxyz
ghost
12345
abcdef12ijklmn3pqr45uvwxyz

$ cat subseq-short
while read s; do
        read p; read r; read o; echo $o; read
        timeout 1s jelly eun $1 "='T€ŒpfṢ€$ḢṬœp³ż⁵$³Ḋ?" "'$s'" "'$p'" "'$r'"
        (($?)) && echo '(killed)'
done < test-cases
$ ./subseq-short
abcdef12ijklmn3pqr45uvwxyz
abcdef12ijklmn3pqr45uvwxyz
BbcOeedcbB
BbcOeedcbB
abcd1e2cbaabcde
abcd1e2cbaabcde
aBc
aBc
abcde
abcde
ABC
ABC
0123T5678901T34567890123456789
0123T5678901T34567890123456789
edcbaedcbaedcbaedcba
edcbaedcbaedcbaedcba
edcb1edc2aed3bae4cba5dcba
edcb1edc2aed3bae4cba5dcba
dcrcdadca
dcrcdadca
aacbcbabcccaabcbabcaabbbbca
(killed)
1ac2cb2bccc33b3bab4aa4bbbc44
(killed)

Wie es funktioniert

='T€ŒpfṢ€$ḢṬœp³ż⁵$³Ḋ?  Main link. Arguments: string s, pattern p, replacement r

='                     Compare each character of s with each character of p.
                       This yields a 2D list. Each row corresponds to a char in p.
  T€                   Compute the truthy indices of each row, i.e., the indices
                       of all occurrences of that char in s.
   Œp                  Compute the Cartesian product of the lists of indices.
        $              Combine the two links to the left into a monadic chain:
      Ṣ€                 Sort each list of indices.
     f                   Filter, removing all non-sorted lists of indices.
         Ḣ             Head; take the first (sorted) list of indices.
          Ṭ            Truth; generate a list with 1's at those indices.
           œp³         Partition; split s at all 1's, removing those characters.
                  Ḋ?   If the partition has more than more than one element:
              ż⁵$        Zip the partition with r.
                 ³       Else, return s.
Dennis
quelle
12

Python 2, 88 Bytes

def f(a,b,c,o=""):
 for q in a:x=q==b[:1];o+=c[:x]or q;b=b[x:];c=c[x:]
 print[o,a][c>'']

Eine Funktion, die die drei Zeichenfolgen aufnimmt und das Ergebnis an STDOUT ausgibt. Die Funktion übergibt die Zeichenfolge einfach einmal, nimmt das entsprechende Zeichen und aktualisiert es, b,cwährend wir fortfahren.

Zum Testen (nach dem Ersetzen printdurch return):

S = """
<test cases here>
"""

for T in S.split("\n\n"):
    A,B,C,D = T.split()
    assert f(A,B,C) == D
Sp3000
quelle
9

Java 7, 141

Ich glaube, ich kann noch mehr damit anfangen, aber ich muss erst einmal davonlaufen. Es ist nur eine einfache Iteration / Ersetzung, die einen Index in A und B führt.

char[]h(char[]a,char[]b,char[]c){char[]d=a.clone();int i=0,j=0,k=b.length;for(;i<a.length&j<k;i++)if(a[i]==b[j])d[i]=c[j++];return j==k?d:a;}

Leerzeichen für Ihr Vergnügen:

char[]h(char[]a,char[]b,char[]c){
    char[]d=a.clone();
    int i=0,j=0,k=b.length;
    for(;i<a.length&j<k;i++)
        if(a[i]==b[j])d[i]=c[j++];
    return j==k?d:a;
}
Geobits
quelle
WhitespacedJa, das ist total lesbar
Katze
Ist es nicht so? Der Hauptgrund, warum ich die mehrzeilige eingerückte Version hinzufüge, besteht darin, horizontales Scrollen zu vermeiden, nur damit alles auf einmal gesehen werden kann. Inline-Whitespace ist keine so große Sache, IMO;)
Geobits
[feature-request] noch mehr whitespace
Alex A.
@AlexA. Hier gehts!
Geobits
@Geobits Speichern Sie ein Byte am Ende, wenn Sie das tunj<k?a:d
Xanderhall
7

Lua, 121 Bytes

Die einfache Lösung gsubermöglicht es uns, jedes Zeichen genau einmal zu durchlaufen und durch eine neue Instanz der Zeichenfolge zu ersetzen.

Es nimmt Eingaben über 3 Befehlszeilenargumente entgegen und gibt eine Zeichenfolge an STDOUT aus.

a,b,c=...d=a:gsub(".",function(s)if b:find(s)then b=b:sub(2)x=c:sub(1,1)c=c:sub(2)return x end end)print(b~=''and a or d)

Ungolfed

a,b,c=...               -- unpack the arguments into a, b and c
d=a:gsub(".",function(s)-- iterate over each character of the first argument
  if b:find(s)then      -- if the current character is in the set b
    b=b:sub(2)          -- remove it from b
    x=c:sub(1,1)        -- save the replacement character in x
    c=c:sub(2)          -- remove it from c
    return x            -- replace the current character with x
  end
end)
print(b~=''             -- if b is empty, we replaced all the character
      and a or d)       -- so output the result of gsub, else, output the first argument
Katenkyo
quelle
6

Python 3, 127 Bytes.

16 Bytes dank Katenkyo gespart.

Der Mensch arbeitete immer noch ein bisschen daran, aber es war so schlimm, als ich es mir vorgestellt hatte.

f=lambda a,b,c:a.replace(b[0],c[0],1)[:a.index(b[0])+1]+f(a[a.index(b[0])+1:],b[1:],c[1:])if b and all(x in a for x in b)else a

Erklärung: Awww ja, Rekursion.

Testfälle:

assert f('abcdeedcba', 'ada', 'BOB') == 'BbcOeedcbB'
assert f('abcdeedcbaabcde', 'ed', '12') == 'abcd1e2cbaabcde'
assert f('012345678901234567890123456789', '42', 'TT') == '0123T5678901T34567890123456789'
assert f('ABC', 'ABCD', '1234') == 'ABC'
Morgan Thrapp
quelle
+1 für Golf 50 off, aber weiter so! Dies muss meine Java-Antwort mindestens schlagen;)
Geobits
7
@Geobits Ja, ich habe noch nie zuvor gegen Java verloren. Das ist meine größte Schande.
Morgan Thrapp
Ich kenne mich nicht wirklich mit Python aus, sondern all(x in a for x in b)überprüfe auch, ob die Elemente in b und a in derselben Reihenfolge erscheinen, oder nur, wenn sie hier sind.
Katenkyo
@Katenkyo Nur, dass sie alle da sind, aber die Bestellung wird durch das Schneiden erledigt, wenn wir wiederkommen.
Morgan Thrapp
Ok, würden Sie nicht auch return a.replace(b[0],c[0],1)[:l(b[0])+1]+f(a[l(b[0])+1:],b[1:],c[1:])if b and all(x in a for x in b)else aein paar Bytes sparen?
Katenkyo
5

Python 3.5, 87 Bytes

import re
lambda s,p,r:re.sub('(.*?)'.join(p),'\g<%d>'.join(r)%(*range(1,len(r)),),s,1)

repl.it um alle Testfälle zu verifizieren .

Wie es funktioniert

  • '(.*?)'.join(p) Erstellt ein Suchmuster, das der zu ersetzenden Teilsequenz und allen Elementen zwischen den Elementen entspricht.

    Da die Quantifizierer faul sind, entspricht jeder (.*?)so wenig Zeichen wie möglich.

    Für das Muster ghostist der konstruierte reguläre Ausdruck g(.*?)h(.*?)o(.*?)s(.*?)t.

  • '\g<%d>'.join(r)%(*range(1,len(r)),) Erstellt die Ersatzzeichenfolge unter Verwendung der Zeichenfolgenformatierung.

    Jedes \g<n>bezieht sich auf die n- te erfasste Gruppe, genau wie \nes der Fall wäre.

    Für den Ersatz 12345ist der konstruierte String 1\g<1>2\g<2>3\g<3>4\g<4>5.

  • re.sub(...,...,s,1)Führt höchstens eine Ersetzung in der Zeichenfolge durch s.

Dennis
quelle
4

Pyth, 27

.xuXG.*HC,hSI#.nM*FxRcQ1zwQ

Test Suite

In der Testsuite werden die letzten beiden Fälle ausgelassen, da der Arbeitsspeicher knapp wird. Der hier verwendete Algorithmus besteht darin, alle Indizes jedes Zeichens in der zweiten Zeichenfolge in der ersten Zeichenfolge zu finden, dann alle möglichen Reihenfolgen dieser Indizes zu finden und nur die zu verwenden, die in sortierter Reihenfolge vorliegen. Verwenden Sie dann die erste davon in sortierter Reihenfolge als Liste der Indizes in der ersten Zeichenfolge, um die Werte aus der dritten Zeichenfolge zu aktualisieren.

Ich denke, es sollte etwas kürzer sein als .nM*F...

FryAmTheEggman
quelle
4

MATL , 33 Bytes

y!=[]0b"@n:!<@*fX<h5Mt?}.]]?iw(}x

Probieren Sie es online!

Erläuterung

y!      % Implicitly input first two strings. Duplicate the first and transpose
=       % Compare the two strings element-wise. Gives a 2D array with all combinations
[]      % Push empty array. Indices of matching elements will be appended to this
0       % Push a 0. This is the index of last character used up in first string
b       % Bubble up (rearrange elements in stack) to move 2D array to top
"       % For each column of that array (each char of the second string)
  @     %   Push current column
  n:!   %   Transform into column array of consecutive values starting from 1
  <     %   Compare with index of last character used up of first string
  @*    %   Push current column again. Multiply element-wise (logical AND)
  fX<   %   Find index of first matching character, or empty if there's none
  h     %   Append to array containing indices of matching elements
  5Mt   %   Push index of matching character again. Duplicate
  ?}    %   If it's empty
    .   %     Break loop
  ]     %   End if
]       % End for
        % The top of the stack now contains a copy of the index of last matching
        % character, or an empty array if there was no match
?       % If non-empty: all characters were matched
  i     %   Input third string
  w     %   Swap top two elements in stack
  (     %   Assign the characters of the third string to first string at found indices
}       % Else: the original string needs to be output
  x     %   Delete (partial) array of matching indices. Leave original string in stack
        % End if
        % Implicitly display (either modified string or original string)
Luis Mendo
quelle
3

JavaScript (ES6), 84 Byte

(a,b,c)=>[...b].every((q,i)=>r[p=a.indexOf(q,p)]=~p++&&c[i],p=0,r=[...a])?r.join``:a

Erklärung / Test

user81655
quelle
3

JavaScript (ES6), 84 76 Bytes

(a,b,c)=>a.replace(RegExp([...b].join`(.*?)`),c.replace(/\B/g,(_,i)=>'$'+i))

Weil ich mir sicher war, dass dies ein Job für RegExp war.

Edit: 8 Bytes gespeichert dank @ MartinBüttner ♦.

Ein Port von @ KevinLaus Ruby-Antwort nahm 82 Bytes in Anspruch:

([...a],[...b],[...c])=>(d=a.map(e=>e==b[0]?c.shift(b.shift()):e),b[0]?a:d).join``

Ich habe auch versucht, eine rekursive RegExp-Lösung, aber das dauerte 90 Bytes:

f=(a,[b,...d],[c,...e])=>b?a.replace(RegExp(b+'(.*'+d.join`.*`+'.*)'),(_,s)=>c+f(s,d,e)):a
Neil
quelle
3

Julia, 89-70 Bytes

f(s,a,b,i=0)=(o=join(["$a "[i+1]!=c?c:b[i+=1]for c=s]);i<endof(a)?s:o)

Verwendet einen Index i, um die Muster- / Ersetzungszeichenfolgen zu durchlaufen. -19 Bytes dank @Dennis!

Sp3000
quelle
2

C 98 Bytes

char*f(i,o,s,r)char*i,*o,*s,*r;{char*I=i,*O=o;for(;*i;++i,++o)*o=*i==*s?++s,*r++:*i;return*s?I:O;}

/ * Erweiterter Code * /

char *f(i, o, s, r)
    char *i, *o, *s, *r;
{
    char *I=i, *O=o;
    for (;  *i;  ++i,++o)
        *o = (*i==*s) ? (++s,*r++) : *i;
    return *s ? I : O;
}

Die Argumente sind: i nput string, o utput Puffer, s earch string, r eplacement.

Nachdem wir uns an den Beginn der Eingabe und Ausgabe erinnert haben, gehen wir die Eingabe durch und ersetzen und erweitern die Substitution, wann immer wir eine treffen. Wenn wir am Ende keine Substitutionen mehr haben, geben Sie den Ausgabepuffer zurück, ansonsten die nicht geänderte Eingabe.

/ * Tests * /

struct T
{
    const char *input;
    const char *search;
    const char *replace;
    const char *expected;
};

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
    int i;
    static const struct T test[] = {
        { "abcdefghijklmnopqrstuvwxyz",
          "ghost",
          "12345",
          "abcdef12ijklmn3pqr45uvwxyz"},
        { "abcdeedcba",
          "ada",
          "BOB",
          "BbcOeedcbB"},
        { "abcdeedcbaabcde",
          "ed",
          "12",
          "abcd1e2cbaabcde"},
        { "121",
          "121",
          "aBc",
          "aBc"},
        { "abcde",
          "acb",
          "123",
          "abcde"},
        { "ABC",
          "ABCD",
          "1234",
          "ABC"},
        { "012345678901234567890123456789",
          "42",
          "TT",
          "0123T5678901T34567890123456789"},
        { "edcbaedcbaedcbaedcba",
          "abcde",
          "12345",
          "edcbaedcbaedcbaedcba"},
        { "edcbaedcbaedcbaedcbaedcba",
          "abcde",
          "12345",
          "edcb1edc2aed3bae4cba5dcba"},
        { "daccdedca",
          "ace",
          "cra",
          "dcrcdadca"},
        { "aacbcbabcccaabcbabcaabbbbca",
          "abaaaccbac",
          "1223334444",
          "aacbcbabcccaabcbabcaabbbbca"},
        { "aacbcbabcccaabcbabcaabbbbcac",
          "abaaaccbac",
          "1223334444",
          "1ac2cb2bccc33b3bab4aa4bbbc44"
        }
    };

    for (i = 0;  i < (sizeof test) / (sizeof test[0]);  ++i) {
        const struct T *t = test+i;
        char *out = malloc(strlen(t->input)+1);
        char *result = f(t->input, out, t->search, t->replace);
        if (strcmp(t->expected, result))
            printf("Failed test %d; result = \"%s\"\n", i, result);
    }
    return EXIT_SUCCESS;
}
Toby Speight
quelle
2

R, 76 Bytes

function(a,b,c){s=substr;for(x in 1:nchar(b)){a=sub(s(b,x,x),s(c,x,x),a)};a}

verwendet suberstes Spiel zu ersetzen

Ungolfed

function(a,b,c){                    # function with 3 arguments as per description
  s=substr;                         # alias for substr (saves 1 byte)
   for(x in 1:nchar(b)){            # index 1 to number character in b
     a=sub(s(b,x,x),s(c,x,x),a)};   # replace first instance of b[x] in a  
                                    # with c[x] and reassign to a
 a}                                 # return a
mnel
quelle
2

C ++, 204 Bytes

Golf gespielt

#include<iostream>
#include<string>
int main(){std::string a, b, c;std::cin>>a>>b>>c;int t=0;for(int x=0;x<b.length();x++){t=a.find(b[x],t);if(t!=-1){a.replace(t,1,c.substr(x,1));}}std::cout<<a;return 0;}

Ungolfed

#include<iostream>
#include<string>

int main()
{
    std::string a, b, c;
    std::cin>>a>>b>>c;
    int t = 0;
    for (int x=0;x<b.length();x++) {
        t = a.find(b[x], t);
        if (t != -1) {
            a.replace(t,1,c.substr(x, 1));
        }
    }
    std::cout<<a;
    return 0;
}
Michelfrancis Bustillos
quelle
Ich glaube nicht, dass Sie stdgenug verwenden, um dies zu rechtfertigen using namespace std;. Unter Verwendung std::cin, std::coutund std::stringwird 5 Bytes speichern , da diejenigen , scheinen die einzigen Verwendungen von diesem Namensraum zu sein.
Wert Tinte
@ KevinLau Danke! Sie haben sehr recht, ich dachte darüber nach, aber ich habe eigentlich nicht damit gerechnet, dass es Zeichen sparen würde.
Michelfrancis Bustillos
Oh! Eine weitere Sache, da es wichtig ist. Nachdem Sie Ihren Code noch einmal durchgelesen haben, ist mir aufgefallen, dass Sie das am weitesten links stehende Vorkommen jedes Buchstabens in bin gierig ersetzen a, aber die späteren Buchstaben müssen auch nach den früheren Buchstaben stehen. (Sehen Sie sich Testfall 3 an und vergleichen Sie ihn mit Ihrer Ausgabe. Ich denke, Sie werden feststellen, dass Ihr Code ausgegeben wird, abc21ed...wenn die erwartete Ausgabe vorliegt abcd1e2...!)
Value Ink,
Generieren Sie in der C ++ 14-Compilereingabe von "Adregffftd \ nA23 \ nzac \ n" über dem Code vor 10 Minuten die Ausgabe von "zdregffftd" anstelle von "Adregffftd"
RosLuP
2

Retina , 63 Bytes

.+$
$&¶;$&
+`^(.)(.*¶)(.)([^;]+);(.*?)\1
$2$4$5$3;
A1`
;

G2=`.

Eingang wird genommen , um B, C, A, getrennt durch Zeilenvorschübe.

Probieren Sie es online aus.

Martin Ender
quelle
2

Haskell, 87 Bytes

x@((a,b):c)#(d:e)|a==d,([],z)<-c#e=([],b:z)|0<1=(d:)<$>x#e
x#y=(x,y)
a!b=snd.(zip a b#)

Ich bemerkte das Fehlen einer Haskell-Antwort und beschloss, das zu beheben. Dies definiert eine ternäre Funktion !mit dem Argument order pattern-replacement-string. Probieren Sie es hier aus.

Erläuterung

Die Hilfsfunktion verwendet #eine Liste xvon Zeichenpaaren (Muster und Ersetzung) und eine Zeichenfolge y. Wenn die "Muster" -Zeichen xeine Untersequenz von bilden y, wird die leere Liste zurückgegeben und yjedes Musterzeichen durch das Gegenstück ersetzt. Andernfalls wird das Paar zurückgegeben (x,y). Die Funktion !zippt die Muster- und Ersetzungszeichenfolgen in die dritte Zeichenfolge und xgilt #für diese xund gibt die zweite Komponente des Ergebnisses zurück.

x@((a,b):c)#(d:e)  -- First case of #: both arguments nonempty.
  |a==d,           -- If the pattern char matches the string's head,
   ([],z)<-c#e     -- and the pattern's tail is a subsequence of the string's tail,
  =([],b:z)        -- tack the replacement char to the recursion result.
  |0<1             -- Otherwise,
  =(d:)<$>x#e      -- recurse with the same pairs and tack string's head to result.
x#y=(x,y)          -- If either argument is empty, just pair them.

Wenn das Muster eine Teilfolge der Zeichenfolge ist, wird der Code in der O (n) -Zeit ausgeführt, wobei ein rekursiver Durchlauf durch die Zeichenfolge erfolgt und die Ersetzung dabei gierig konstruiert wird. Wenn das Muster jedoch keine Untersequenz ist, läuft es im schlimmsten Fall in O (2 n ) -Zeit. Dies liegt daran, dass die Funktion sich an jeder Stelle, an der das Muster und die Zeichenfolge übereinstimmen, selbst aufruft, um zu überprüfen, ob das Muster tatsächlich eine Teilsequenz ist.

Zgarb
quelle
2

JavaScript (ES6), 100 bis 95 Byte

(a,b,c)=>1?(t=[...a].map(e=>b[0]==e?(u=c[0],b=b.slice(1),c=c.slice(1),u):e).join``,b==""?t:a):a

Dies ist eine gültige JavaScript-Lambda-Funktion. Ausgänge als Funktion return. Nimmt drei Argumente auf ( a,b,c). Fügen Sie f=am Anfang und rufen Sie wie f(arg1,arg2,arg3).

f=(a,b,c)=>1?(t=[...a].map(e=>b[0]==e?(u=c[0],b=b.slice(1),c=c.slice(1),u):e).join``,b==""?t:a):a

console.log(f(prompt("Value for A"),prompt("Value for B"),prompt("Value for C")))

Arjun
quelle
Willkommen bei PPCG! Unbenannte Funktionen sind in der Regel akzeptabel . Sie benötigen die, es f=sei denn, Ihre Funktion ist rekursiv, sie sieht jedoch anders aus.
Martin Ender
@ MartinBüttner Danke! :) Aktualisiert meine Antwort.
Arjun
Leider aschlägt dies fehl, wenn das Muster nicht enthalten ist. Ich bin mir auch nicht sicher, ob es akzeptabel ist, eine Reihe von Zeichenfolgen zurückzugeben.
Dennis
@ Tennis Ich habe meine Lösung aktualisiert. Ich denke, es ist jetzt richtig. Entschuldigen Sie die verspätete Antwort und Aktualisierung. (Ich habe gerade Ihren Kommentar bemerkt, daher die Verzögerung)
Arjun
@MartinEnder Als ich alle meine Lösungen durchgesehen habe, habe ich festgestellt, dass diese nicht korrekt sind. Aber ich habe es jetzt korrigiert; und es ist fünf Bytes kürzer (da ich viele Golfplätze unberührt gelassen hatte; ich war zu dieser Zeit ein Anfänger im Golfen; nicht, dass ich jetzt ein großartiger bin: p). Entschuldigung, dass Sie eine falsche Lösung gepostet haben.
Arjun
2

C (gcc), 67 62 61 59 Bytes

f(s,a,b)char*s,*a,*b;{*s==*a?*s=*b++,a++:1;*a&&f(s+1,a,b);}

Probieren Sie es online!

betseg
quelle
1

Oktave, 97 Bytes

function A=U(A,B,C)t=0;for s=B if p=find(A(t+1:end)==s,1) D(t=p+t)=~0;else return;end;end;A(D)=C;

Iterieren Sie über die zu ersetzende Teilsequenz. finde das erste Vorkommen des ersten Zeichens, finde das nächste Zeichen in der verbleibenden Zeichenkette, wiederhole. Das einzig interessante daran ist:

D(t=p+t)=~0

D(     )      %// D is a logical mask of characters to replace in the input string
  t=p+t       %// t is the current end of D 
              %// p is the location of the character to replace
              %// update t and use as index to grow D
        =~0   %// make it so, number 1

Da ideone immer noch keine Funktionen mit anderen Namen als '' akzeptiert, lasse ich hier nur einen Probelauf. Eingaben werden der Kürze halber nur für die ersten Testfälle angezeigt. keyist die erwartete Ausgabe, ansist die Funktionsausgabe.

A = abcdefghijklmnopqrstuvwxyz
B = ghost
C = 12345
key = abcdef12ijklmn3pqr45uvwxyz
ans = abcdef12ijklmn3pqr45uvwxyz
A = abcdeedcba
B = ada
C = BOB
key = BbcOeedcbB
ans = BbcOeedcbB
A = abcdeedcbaabcde
B = ed
C = 12
key = abcd1e2cbaabcde
ans = abcd1e2cbaabcde
key = aBc
ans = aBc
key = abcde
ans = abcde
key = ABC
ans = ABC
key = 0123T5678901T34567890123456789
ans = 0123T5678901T34567890123456789
key = edcbaedcbaedcbaedcba
ans = edcbaedcbaedcbaedcba
key = edcb1edc2aed3bae4cba5dcba
ans = edcb1edc2aed3bae4cba5dcba
key = dcrcdadca
ans = dcrcdadca
key = aacbcbabcccaabcbabcaabbbbca
ans = aacbcbabcccaabcbabcaabbbbca
key = 1ac2cb2bccc33b3bab4aa4bbbc44
ans = 1ac2cb2bccc33b3bab4aa4bbbc44
Becherglas
quelle
Diese Oktavaufgaben an unerwarteten Orten ( D(t=...)) verwirren mich immer wieder :-)
Luis Mendo
1
@ LuisMendo haha ​​... es ist fast wie ... ein Stapel! :)
Becher
1

Python 3, 123 Bytes

Ein anderer Ansatz, den ich teilen wollte, der einige Bytes kürzer ist. Es gibt keine Regeln gegen Standardbibliothek / Regex, oder?

import re
j=''.join
m='(.*?)'
def f(A,B,C):
 *r,l=(re.findall(m+m.join(B)+'(.*)',A)or[[A]])[0]
 print(j(map(j,zip(r,C)))+l)

PS. Dies ist mein erster Golf. Informieren Sie mich über mögliche Probleme / Verbesserungen.

Marc J
quelle
1

Pyth, 22 Bytes

|eJ:Ej"(.*?)"+E\$3s.iJ

Überprüfen Sie alle Testfälle im Pyth-Compiler .

Hintergrund

Wir erstellen einen regulären Ausdruck aus dem Muster, indem wir ein anfügen $und (.*?)zwischen alle Zeichen setzen. Dieser reguläre Ausdruck entspricht der zu ersetzenden Teilsequenz und allen Elementen zwischen den Elementen und allen Elementen bis zum Ende der Zeichenfolge.

Da die Quantifizierer faul sind, entspricht jeder (.*?)so wenig Zeichen wie möglich.

Für den Mustergeist ist der konstruierte reguläre Ausdruck g(.*?)h(.*?)o(.*?)s(.*?)t(.*?)$.

Wenn das Muster mit der Eingabe übereinstimmt, gibt das Builtin r<str><regex>3ein Array zurück, das das Prematch (alles vor der Subsequenz), alle erfassten Gruppen (alles zwischen und nach der Subsequenz) und das Postmatch (die leere Zeichenfolge) enthält.

Wenn das Muster nicht übereinstimmt, gibt das Builtin ein Singleton-Array zurück, das die ursprüngliche Eingabe enthält.

Wie es funktioniert

|eJ:Ej"(.*?)"+E\$3s.iJQ  (implicit) Store the first line of input in Q.

             +E\$        Read the third line of input (pattern) and append '$'.
     j"(.*?)"            Join the result, separating by "(.*?)".
    E                    Read the third line of input (string).
   :             3       Match the string against the regex, as detailed above.
  J                      Save the returned array in J.
 e                       Extract the last element of J. This is an empty string
                         for a successful match or the original string.
|                        Logical OR; replace an empty string with the following:
                   .iJQ    Interleave J and the replacement.
                  s        Flatten the resulting array of strings.
Dennis
quelle
1

Jelly , 23 Bytes

Ṭœpż⁵
0ẋai1
⁴='-;ç\ñ⁴P?

Dies ist zwei Bytes länger als meine andere Gelee-Antwort , endet aber sofort. Probieren Sie es online!

Nachprüfung

$ head -n 5 test-cases
abcdefghijklmnopqrstuvwxyz
ghost
12345
abcdef12ijklmn3pqr45uvwxyz

$ cat subseq-fast
while read s; do
        read p; read r; read o; echo $o; read
        timeout 10s jelly eun $1 "Ṭœpż⁵¶0ẋai1¶⁴='-;ç\ñ⁴P?" "'$p'" "'$s'" "'$r'"
        (($?)) && echo '(killed)'
done < test-cases
$ ./subseq-fast
abcdef12ijklmn3pqr45uvwxyz
abcdef12ijklmn3pqr45uvwxyz
BbcOeedcbB
BbcOeedcbB
abcd1e2cbaabcde
abcd1e2cbaabcde
aBc
aBc
abcde
abcde
ABC
ABC
0123T5678901T34567890123456789
0123T5678901T34567890123456789
edcbaedcbaedcbaedcba
edcbaedcbaedcbaedcba
edcb1edc2aed3bae4cba5dcba
edcb1edc2aed3bae4cba5dcba
dcrcdadca
dcrcdadca
aacbcbabcccaabcbabcaabbbbca
aacbcbabcccaabcbabcaabbbbca
1ac2cb2bccc33b3bab4aa4bbbc44
1ac2cb2bccc33b3bab4aa4bbbc44

Wie es funktioniert

⁴='-;ç\ñ⁴P?  Main link. Arguments: pattern p, string s, replacement r

⁴='          Compare each character of s with each character of p.
             This yields a 2D list. Each row corresponds to a char in p.
   -;        Prepend -1 to the 2D list, yielding a ragged array.
     ç\      Cumulatively reduce the array by the second helper link.
         P?  If the product of the resulting list is non-zero:
       ñ       Call the first helper link with the list and s as arguments.
        ⁴      Else, return s.


Ṭœpż⁵        First helper link. Arguments: L (list of indices), r (replacement)

Ṭ            Truth; generate a list with 1's at those indices.
 œp          Partition; split s at all 1's, removing those characters.
   ż⁵        Zip the partition with r.


0ẋai1        Second helper link. Arguments: n (integer), B (list of Booleans)

0ẋ           Generate a list of n zeroes.
  a          Perform logical AND with B.
             This zeroes out the with n elements of B.
   i1        Compute the first index of 1.
Dennis
quelle
1

Java 7, 102 Bytes

void L(char[]s,char[]l,char[]r){for(int x=0,y=0;x<s.length&&y<l.length;x++)if(s[x]==l[y])s[x]=r[y++];}

Ausführlicher Versuch hier

// String, Lookup, Replacement
void L(char[]s, char[]l, char[]r)
{
    for(int x=0, y=0; x < s.length && y < l.length; x++)
        if(s[x] == l[y])
            s[x] = r[y++];
}
Khaled.K
quelle
1

Julia, 93 90 86 Bytes

f(s,p,r)=(try s=join([match(Regex(join("^$p\$","(.*?)")),s).captures';[r...""]])end;s)

Separat testen zu müssen, ob das Match erfolgreich war, zerstört das Ergebnis. Eine Substitution würde ein Casting erfordern Base.SubstitutionString, was sich wahrscheinlich nicht lohnt ...

Testlauf

julia> f(s,p,r)=(try s=join([match(Regex(join("^$p\$","(.*?)")),s).captures';[r...""]])end;s)
f (generic function with 1 method)

julia> f("aacbcbabcccaabcbabcaabbbbca","abaaaccbac","1223334444")
"aacbcbabcccaabcbabcaabbbbca"

julia> f("aacbcbabcccaabcbabcaabbbbcac","abaaaccbac","1223334444")
"1ac2cb2bccc33b3bab4aa4bbbc44"
Dennis
quelle
1

Julia, 62 59 58 Bytes

f(s,p,r)=(try s[[i=findnext(s,c,i+1)for c=p]'],i=r,0end;s)

I / O besteht aus Zeichenfeldern.

Nachprüfung

julia> f(s,p,r)=(try s[[i=findnext(s,c,i+1)for c=p]'],i=r,0end;s)
f (generic function with 2 methods)

julia> F(s,p,r)=join(f([s...],[p...],[r...])) # string/char array conversion
F (generic function with 1 method)

julia> F("aacbcbabcccaabcbabcaabbbbca","abaaaccbac","1223334444")
"aacbcbabcccaabcbabcaabbbbca"

julia> F("aacbcbabcccaabcbabcaabbbbcac","abaaaccbac","1223334444")
"1ac2cb2bccc33b3bab4aa4bbbc44"
Dennis
quelle
1

PHP, 130 109 Bytes

Ich würde es immer noch gerne kürzer haben; könnte 3 Bytes ( ""<) einsparen, wenn Bgarantiert nicht enthalten wäre 0.

for($s=($a=$argv)[1];""<$c=$a[2][$i++];)if($p=strpos(_.$s,$c,$p+1))$s[$p-1]=$a[3][$k++];echo$k<$i-1?$a[1]:$s;

Übernimmt Argumente von der Kommandozeile. Laufen Sie mit -r.

Ersetzt die Zeichen, wenn sie gefunden werden.
druckt Kopie, wenn alle Zeichen ersetzt wurden; Original sonst.

Titus
quelle
1

Ruby, 70 64 59 58 Bytes

Anonyme Funktion. Gehen Sie durch die Zeichenfolge aeine neue Zeichenfolge zu bauen mit Buchstaben in Übereinstimmung zum nächsten Zeichen ersetzt in bund cdann , wenn alle Zeichen in bam Ende erschöpft, kehren das neu errichteten Zeichenfolge, sonst gibt die ursprüngliche Zeichenfolge.

@histocrat half beim Speichern von 6 Bytes über gsub.

1 Byte dank @Cyoce gespeichert.

->a,b,c{i=0;s=a.gsub(/./){$&==b[i]?c[~-i+=1]:$&};b[i]?a:s}

Probieren Sie es online!

Wert Tinte
quelle
Sie können durch Ersetzen eines Byte speichern -1+i+=1mit~-i+=1
Cyoce
0

Perl, 80 + 1 = 81 Bytes

Laufen Sie mit der -pFlagge

$a=join"(.*?)",split//,<>;$b.=$_." .\$".++$;."."for split//,<>;chop$b;s/$a/$b/ee

Probieren Sie es online!

Der Code generiert prozedural einen Befehl zum Suchen und Ersetzen von Regex, den er dann im letzten Codebit ausführt.

Die Zeichenfolge ghostim ersten Beispiel wird in eine Zeichenfolge umgewandelt g(.*?)h(.*?)o(.*?)s(.*?)t(.*?), dh ggefolgt von 0 oder mehr Zeichen, gefolgt von h0 oder mehr Zeichen, gefolgt von usw. Der *?Quantifizierer bedeutet, dass die Suche nicht gierig und "verschlingen" sein sollte msgstr "so wenig Zeichen wie möglich, anstatt so viel wie möglich abzugleichen.

Die Zeichenfolge wird 12345dann in umgewandelt 1 .$1.2 .$2.3 .$3.4 .$4.5 .$5, die ausgewertet wird, nachdem der reguläre Ausdruck ausgeführt wurde. Jedes von $1,$2,$3,$4,$5ist tatsächlich ein Rückverweis auf eine Erfassungsgruppe (in Klammern) aus der ersten Zeichenfolge.

Gabriel Benamy
quelle
Ich schlage vor , diesen Code ein paar Bytes zu speichern: perl -pe 'eval"s/".<>=~s/.\K/(.*?)/gr."/".<>=~s/.\K/"\${".++$i."}"/gre."/"'. Kam alleine mit, aber es ist ziemlich nah an deiner, also werde ich es nicht posten, das wären zwei sehr nahe beieinander liegende Antworten, aber zögern Sie nicht, Ihre zu bearbeiten!
Dada
Ich habe es gerade ausprobiert, weil ich es als "verwandte" Frage zu einem kürzlich aufgetretenen Problem gesehen habe. Das Beste, was ich bekommen habe, warperl -E 'chomp(($f,$t,$s)=(<>));$f=join"(.*?)",split"",$f;@r=split"",$t;@t=shift@r;push@t,"\${",++$x,"}"for(@r);$t=join"",@t;say$s=~s/$f/$t/r;'
Will Crawford
0

Clojure, 113 Bytes

#(apply str((reduce(fn[[b c r]a](if(=(first b)a)[(rest b)(rest c)(conj r(first c))][b c(conj r a)]))[%2%3[]]%)2))

Eine grundlegende reduce, nicht allzu glücklich über all die lange first, restund conjFunktionsaufrufe. Ich hoffe auf einen besseren Ansatz.

NikoNyrh
quelle