Biorąc pod uwagę łańcuchy X i Y, określ, czy X jest podsekwencją Y. Pusty łańcuch jest traktowany jako podsekwencja każdego łańcucha. (Np. ''I 'anna'są podsekwencjami 'banana'.)

Wkład

• X, być może pusty ciąg alfanumeryczny z rozróżnianiem wielkości liter
• Y, być może pusty ciąg alfanumeryczny z rozróżnianiem wielkości liter

Wydajność

• Prawda czy fałsz (lub odpowiedniki), poprawnie wskazując, czy X jest podsekwencją Y.

Przykłady we / wy

X      Y        output

''     'z00'    True
'z00'  'z00'    True 
'z00'  '00z0'   False
'aa'   'anna'   True
'anna' 'banana' True
'Anna' 'banana' False

Kryteria

• Najkrótszy program wygrywa, zgodnie z liczbą bajtów kodu źródłowego.

Przykładowe programy

• Kilka programów, które można dostosować, znajduje się w tej powiązanej publikacji .

Perl 5 , 17 bajtów (+1?), Pełny program

s//.*/g;$_=<>=~$_

Wypróbuj online!

Wywołaj pflagę do interpretera perla, jak w perl -pe 's//.*/g;$_=<>=~$_'. Zgodnie z ustalonymi regułami punktacji, kiedy to wyzwanie zostało pierwotnie opublikowane , ta flaga kosztuje jeden dodatkowy bajt. Zgodnie z nowszymi zasadami , AFAICT, może być bezpłatny.

Tak czy inaczej, ciągi wejściowe powinny być dostarczane w osobnych liniach zakończonych znakiem nowej linii na standardowym wejściu. Wyjście (na standardowe wyjście) będzie, 1jeśli pierwszy ciąg wejściowy jest podciągiem drugiego, lub w ogóle nic, jeśli nie jest.

Zauważ, że obie linie wejściowe muszą mieć na końcu nową linię, w przeciwnym razie program nie będzie działał poprawnie. Alternatywnie możesz dodać lflagę wiersza poleceń do wywołania, aby perl usunął nowe linie; w zależności od obowiązujących reguł punktacji może to kosztować jeden dodatkowy bajt lub nie. Zauważ, że użycie tej flagi spowoduje również dodanie nowego wiersza do wyniku.

Wersja oryginalna (fragment, 18 bajtów / znaków)

$x=~s//.*/g,$y=~$x

Dane wejściowe są podawane w zmiennych, $xa $ywynikiem jest wartość wyrażenia (w kontekście skalarnym). Uwaga, która $xjest modyfikowana w procesie. (Tak, wiem, że użycie $_zamiast $xpozwoli mi zaoszczędzić cztery znaki, ale zrobienie tego we fragmencie, który wydaje mi się zbyt tandetny).

Jak to działa?

Pierwsza część $x=~s//.*/gwstawia ciąg znaków .*między każdym znakiem $x. Druga część, $y=~$xtraktuje $xjako wyrażenie regularne i dopasowuje się $ydo niego. W wyrażeniach regularnych Perl .*dopasowuje zero lub więcej dowolnych znaków, podczas gdy wszystkie znaki alfanumeryczne wygodnie pasują do siebie.

Ruby, 32 znaki

s=->x,y{y=~/#{[*x.chars]*".*"}/}

To rozwiązanie zwraca, niljeśli xnie jest to podsekwencja, ya liczba jest inna (tj. Rubinowe odpowiedniki falsei true). Przykłady:

p s['','z00']        # => 0   (i.e. true)
p s['z00','z00']     # => 0   (i.e. true)
p s['z00','00z0']    # => nil (i.e. false)
p s['anna','banana'] # => 1   (i.e. true)
p s['Anna','banana'] # => nil (i.e. false)

Haskell, 51 37

h@(f:l)%(g:m)=f==g&&l%m||h%m;x%y=x<=y

Dzięki Hammar za znaczną poprawę. Jest to teraz funkcja poprawki, ale wydaje się, że nie ma powodu, dla którego nie powinna.

Demonstracja:

GHCi> :{
GHCi| zipWith (%) [""   , "z00", "z00" , "anna"  , "Anna"]
GHCi|             ["z00", "z00", "00z0", "banana", "banana"]
GHCi| :}
[True,True,False,True,False]

Python (48 znaków)

import re;s=lambda x,y:re.search('.*'.join(x),y)

Takie samo podejście jak odpowiedź Ruby Howarda. Szkoda, że ​​Python musi zaimportować pakiet wyrażeń regularnych i jego „szczegółowe” lambda. :-)

Python, 59 znaków

def s(x,y):
 for c in y:
  if x:x=x[c==x[0]:]
 return x==""

Uznałem, że moja odpowiedź będzie lepiej wyrażona w Pythonie.

Edycja: Dodano sugestie res.

GolfScript (22 znaki)

X[0]+Y{1$(@={\}*;}/0=!

Zakłada się, że dane wejściowe są traktowane jako dwie predefiniowane zmienne Xi Ychociaż jest to dość niezwykłe w GolfScript. Pozostawia na stosie wartość 1prawda lub 0fałsz.

C (52 znaki)

s(char*x,char*y){return!*x||*y&&s(*x-*y?x:x+1,y+1);}

Przypadki testowe

Burleska (6 znaków)

6 znaków w Burlesce: R@\/~[ (zakładając, że xiy znajdują się na stosie. Zobacz tutaj w akcji.)

C, 23:

while(*y)*x-*y++?0:x++;

wynik w * x

http://ideone.com/BpITZ

PHP, 90 znaków

<?function s($x,$y){while($a<strlen($y))if($y[$a++]==$x[0])$x=substr($x,1);return $x=="";}

Scala 106:

def m(a:String,b:String):Boolean=(a.size==0)||((b.size!=0)&&((a(0)==b(0)&&m(a.tail,b.tail))||m(a,b.tail)))

CoffeeScript 112 100 95 89

Moja pierwsza próba golfa kodowego ... mam nadzieję, że nie zawstydzę mojej rodziny!

z=(x,y)->a=x.length;return 1if!a;b=y.indexOf x[0];return 0if!++b;z x[1..a],y[b..y.length]

Edycja : okazuje się, że Coffeescript jest bardziej wybaczający niż myślałem z białymi znakami.

Podziękowania dla res i Petera Taylora za kilka wskazówek, dzięki którym będzie trochę bardziej elegancki

C #, 70 113 107 90 znaków

static bool S(string x,string y){return y.Any(c=>x==""||(x=x.Remove(0,c==x[0]?1:0))=="");}

Matematyka 19 17 27

LongestCommonSequencezwraca najdłuższą nieciągłą podsekwencję dwóch łańcuchów. (Nie mylić z tym LongestCommonSubsequence, co zwraca najdłuższą ciągłą podsekwencję.

Poniższe sprawdza, czy najdłuższy ciągły podciąg jest pierwszym z dwóch ciągów. (Więc musisz wprowadzić krótszy ciąg, a następnie większy ciąg).

LongestCommonSequence@##==#& 

Przykłady

LongestCommonSequence@## == # &["", "z00"]
LongestCommonSequence@## == # &["z00", "z00"]
LongestCommonSequence@## == # &["anna", "banana"]
LongestCommonSequence@## == # &["Anna", "banana"]

Prawda Prawda Prawda Fałsz

Krytyczny test jest trzeci, ponieważ „anna” jest zawarta niejednoznacznie w „bananie”.

Python 3.8 (wersja wstępna) , 42 bajty

lambda a,b:''in[a:=a[a[:1]==c:]for c in b]

Wypróbuj online!

Python 3.8 (wersja wstępna) , 48 bajtów

lambda a,b,j=0:all((j:=1+b.find(c,j))for c in a)

Wypróbuj online!

Python 2 , 48 bajtów

lambda a,b:re.search('.*'.join(a),b)>0
import re

Wypróbuj online!

Skopiowano z tej odpowiedzi Lynn . >0Mogą być pominięte, jeśli tylko truthy / falsey wyjście jest OK.

Python 2 , 50 bajtów

f=lambda a,b:b and f(a[a[:1]==b[0]:],b[1:])or''==a

Wypróbuj online!

Python 2 , 50 bajtów

lambda a,b:reduce(lambda s,c:s[c==s[:1]:],b,a)==''

Wypróbuj online!

C - 74 71 64

To nie jest lepsze niż rozwiązanie Petera Taylora, ale myślę, że to całkiem zabawne (plus, to kompletny działający program, a nie tylko funkcja)

main(int c,char**v){for(;*v[1]!=0;++v[1])v[2]+=*v[1]==*v[2];return*v[2];}

main(int c,char**v){for(;*v[1];++v[1])v[2]+=*v[1]==*v[2];return*v[2];}

main(c,v)char**v;{while(*v[1])v[2]+=*v[1]++==*v[2];return*v[2];}

I bez golfa:

main(int argc, char** argv){
   char * input = argv[1];
   char * test  = argv[2];

   // advance through the input string. Each time the current input
   // character is equal to the current test character, increment
   // the position in the test string.

   for(; *input!='\0'; ++input) test += *input == *test;

   // return the character that we got to in the test string.
   // if it is '\0' then we got to the end of the test string which
   // means that it is a subsequence, and the 0 (EXIT_SUCCESS) value is returned
   // otherwise something non-zero is returned, indicating failure.
   return *test;
}

Aby to przetestować, możesz zrobić coś takiego:

./is_subsequence banana anna && echo "yes" || echo "nope"    
# yes
./is_subsequence banana foobar && echo "yes" || echo "nope"    
# nope

Pyton, 66 62 59 58 znaków

To zabawne rozwiązanie, zdecydowanie fajny problem.

def f(n,h,r=0):
 for c in h:r+=n[r:r+1]==c
 return r==len(n)

Rubinowy 32 30 28

f=->a,b{b.match a.tr'','.*'}

Zwróci MatchDatainstancję, jeśli ajest to podsekwencja blub w nilinny sposób.

Stara wersja, która zamiast podciągów znajduje podciąg

Rubin 15

f=->a,b{!!b[a]}

Używając String#[](str)metody, która zwraca strif strjest podciągiem selfi !!zwraca, Booleanjeśli zwracana wartość może być użyta jako boolean (i nie musi być truelub false), to może być tylko 13 znaków:

f=->a,b{b[a]}

Zwróci, niljeśli anie jest podciągiem b.

SWI-Prolog, SICStus

Wbudowana sublist predykatu / 2 SICStus sprawdza, czy wszystkie elementy z pierwszej listy pojawiają się również na drugiej liście. Ten predykat jest również dostępny w SWI-Prolog za pośrednictwem biblioteki kompatybilności, którą można załadować za pomocą zapytania [library(dialect/sicstus/lists)]..

Przykładowy przebieg:

25 ?- sublist("","z00").
true.

26 ?- sublist("z00","z00").
true .

27 ?- sublist("z00","00z0").
false.

28 ?- sublist("aa","anna").
true .

29 ?- sublist("anna","banana").
true .

30 ?- sublist("Anna","banana").
false.

Liczba bajtów może technicznie wynosić 0, ponieważ wszystko, co tutaj robimy, to zapytania, podobnie jak uruchamiamy program i dostarczamy do niego dane wejściowe.

PHP, 41 bajtów

drukuje 1 za prawdę i nic za fałsz

<?=!levenshtein($argv[1],$argv[2],0,1,1);

Jeśli wykonano tylko wstawienia od słowa 1 do słowa 2, w prawdziwych przypadkach liczba wynosi zero

lewenshtein

Wypróbuj online!

PHP, 57 bajtów

wypisuje 1 dla true i 0 dla false

Tworzy Regex

<?=preg_match(_.chunk_split($argv[1],1,".*")._,$argv[2]);

Wypróbuj online!

Brachylog , 2 bajty

⊆ᵈ

Wypróbuj online!

Podobnie jak w przypadku tej odpowiedzi, ⊆ jest wbudowanym predykatem, który deklaruje związek między zmiennymi wejściowymi i wyjściowymi, i ᵈjest meta-predykatem, który modyfikuje go, aby zadeklarować tę samą relację między pierwszym i drugim elementem zmiennej wejściowej (i ujednolicić zmienna wyjściowa z drugim elementem, ale ponieważ jest to problem decyzyjny, który nie ma tutaj znaczenia). X⊆Yjest twierdzeniem, że X jest podsekwencją Y, dlatego tak jest [X,Y]⊆ᵈ.

Ten predykat (który jest generowany przez sukces lub niepowodzenie, który jest drukowany true.lub false.gdy jest uruchamiany jako program) przyjmuje dane wejściowe jako listę dwóch ciągów. Jeśli wprowadzanie danych jest nieco bardziej elastyczne ...

Brachylog , 1 bajt

⊆

Wypróbuj online!

Pobiera ciąg X jako zmienną wejściową, a ciąg Y jako zmienną wyjściową. Wynika z sukcesu lub porażki, jak poprzednio. Jeśli działa jako pełny program, X jest podawany jako dane wejściowe, a Y jako pierwszy argument wiersza poleceń.

CoffeeScript 73

Oto alternatywna odpowiedź CoffeeScript z użyciem wyrażeń regularnych zamiast rekurencji:

z=(x,y)->a='.*';a+=c+'.*'for c in x;b=eval('/'+a+'/');(y.replace b,'')<y

Jeśli stóg siana pasuje do bardzo chciwego wyrażenia regularnego zbudowanego z igły, zostanie zastąpiony pustym ciągiem. Jeśli stóg siana jest krótszy niż się zaczął, igła była podsekwencją.

Zwraca wartość false, gdy xiy to zarówno pustych strun. Pomyśl, że potrzebujemy filozofa, który powie nam, czy pusty łańcuch jest podsekwencją samego siebie!

(Wysłany jako oddzielna odpowiedź od mojej poprzedniej, ponieważ wydaje się wystarczająco inny, aby to uzasadnić).

PowerShell, 38

$args[1]-clike($args[0]-replace'','*')

Oczywiście każde takie rozwiązanie oparte na wyrażeniach regularnych lub wzorcach ma poważne problemy z wydajnością przy dłuższych ciągach. Ale ponieważ kryterium stanowi krótkość ...

Rodzaj anty-rozwiązania generującego wszystkie podsekwencje Y:

Python 93

l=len(y)
print x in[''.join(c for i,c in zip(bin(n)[2:].rjust(l,'0'),y)if i=='1')for n in range(2**l)]

APL (31)

Trochę brakuje obsługi ciągów w APL.

{(⊂'')∊N←⍵↓⍨¨1,⍨=/⊃¨⍵:~×⍴⊃N⋄∇N}

stosowanie:

      {(⊂ '') ∊N ← ⍵ ↓ ⍨¨1, ⍨ = / ⊃¨⍵: ~ × ⍴⊃N⋄∇N} „anna” „banana”
1
      {(⊂ '') ∊N ← ⍵ ↓ ⍨¨1, ⍨ = / ⊃¨⍵: ~ × ⍴⊃N⋄∇N} „Anna” „banana”
0
      {(⊂ '') ∊N ← ⍵ ↓ ⍨¨1, ⍨ = / ⊃¨⍵: ~ × ⍴⊃N⋄∇N} '' 'banana'
1

Python 132

Podobne do Daniero's. Nie jest to najłatwiejsze rozwiązanie, ale fajnie było spróbować. Jestem nowy w Pythonie, więc jestem pewien, że mógłbym go skrócić, gdybym wiedział trochę więcej.

def f(i):
    s=x;j=0
    while j<len(s):t=~i%2;s=[s[:j]+s[j+1:],s][t];j+=t;i>>=1
    return s==y
print True in map(f,range(1,2**len(x)))

Python - 72

def f(a,b):
 c=len(a)
 for i in b:a=a.replace(i,"",1)
 print len(a+b)==c

Python ( 75 52)

s=lambda a,b:a==''or b>''and s(a[a[0]==b[0]:],b[1:])

Proste rozwiązanie rekurencyjne. Po raz pierwszy gra w golfa, więc wszelkie wskazówki dotyczące zmniejszania tego są bardzo mile widziane :)

Testowane z następującymi:

assert s('anna', 'banana') == True
assert s('oo0', 'oFopp0') == True
assert s 'this', 'this is a string') == True
assert s('that', 'this hat is large') == True
assert s('cba', 'abcdefg') == False

Dzięki @lirtosiast za kilka sprytnych sztuczek boolowskich.

PHP, 75 65 64 bajtów

for(;$p=@strpos(_.$argv[2],$c=$argv[1][$i++],$p+1););echo""==$c;

pobiera dane wejściowe z argumentów wiersza poleceń; wypisuje 1dla true, pusty łańcuch dla false. Uruchom z -r.

wyjaśnienie:

• strposzwraca, falsejeśli igła $cnie znajduje się w stogu siana $argv[2](po pozycji $p),
  co powoduje przerwanie pętli.
• strposzwraca falsetakże pustą igłę, przerywając pętlę na końcu$argv[1] .
• Jeśli $argv[1]jest podsekwencją $argv[2], $cbędzie puste, gdy pęka pętla.
• strposmusi @ukryć Empty needleostrzeżenie.

Szybki, 27

print(Y.range(of:X) != nil)