Diberikan string X dan Y, tentukan apakah X adalah urutan dari Y. String kosong dianggap sebagai urutan dari setiap string. (Misalnya, ''dan 'anna'merupakan lanjutan dari 'banana'.)

Memasukkan

• X, string alfanumerik sensitif-huruf yang mungkin kosong
• Y, string alfanumerik sensitif-huruf yang mungkin kosong

Keluaran

• Benar atau Salah (atau yang setara), dengan benar menunjukkan apakah X adalah kelanjutan dari Y.

Contoh I / O

X      Y        output

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

Kriteria

• Program terpendek menang, sebagaimana ditentukan oleh jumlah byte kode sumber.

Contoh program

• Beberapa program yang bisa diadaptasi ada dalam posting terkait ini .

Perl 5 , 17 byte (+1?), Program lengkap

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

Cobalah online!

Panggil dengan pbendera ke penerjemah perl, seperti pada perl -pe 's//.*/g;$_=<>=~$_'. Sesuai aturan penilaian yang ditetapkan saat tantangan ini awalnya diposting , flag ini dikenai biaya satu byte tambahan. Di bawah aturan yang lebih baru , AFAICT, mungkin gratis.

Either way, string input harus dipasok pada baris-baris terpisah baru pada stdin. Output (ke stdout) akan menjadi 1jika string input pertama adalah substring dari yang kedua, atau tidak sama sekali jika tidak.

Perhatikan bahwa kedua jalur input harus memiliki baris baru di akhir, atau program tidak akan berfungsi dengan benar. Atau, Anda dapat menambahkan lbendera baris perintah ke doa untuk membuat perl strip baris baru; tergantung pada aturan penilaian yang berlaku, ini mungkin atau mungkin tidak dikenakan biaya satu byte tambahan. Perhatikan bahwa menggunakan flag ini juga akan menambahkan baris baru ke output.

Versi asli (snippet, 18 byte / karakter)

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

Input diberikan dalam variabel $xdan $y, hasilnya adalah nilai ekspresi (dalam konteks skalar). Catatan yang $xdimodifikasi dalam proses. (Ya, saya tahu menggunakan $_bukannya $xakan membiarkan saya menghemat empat karakter, tetapi melakukannya dalam potongan yang terasa agak terlalu murahan bagi saya.)

Bagaimana cara kerjanya?

Bagian pertama $x=~s//.*/g,, menyisipkan string .*antara setiap karakter dalam $x. Bagian kedua $y=~$x,, memperlakukan $xsebagai regexp dan cocok $ydengan itu. Di Perl regexps, .*cocok dengan nol atau lebih karakter arbitrer, sementara semua karakter alfanumerik cocok dengan diri mereka sendiri.

Ruby, 32 karakter

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

Solusi ini kembali niljika xbukan ymerupakan urutan dari dan nomor sebaliknya (yaitu setara ruby ​​dengan falsedan true). Contoh:

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

Terima kasih kepada Hammar untuk peningkatan yang substansial. Sekarang fungsi infiks, tetapi sepertinya tidak ada alasan mengapa tidak.

Demonstrasi:

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

Python (48 karakter)

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

Pendekatan yang sama seperti jawaban Ruby Howard. Sayang sekali tentang kebutuhan Python untuk mengimpor paket regex dan "verbose" -nya lambda. :-)

Python, 59 karakter

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

Saya pikir jawaban saya akan lebih baik diungkapkan dengan Python.

Edit: Menambahkan saran res.

GolfScript (22 karakter)

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

Mengasumsikan input diambil sebagai dua variabel yang telah ditentukan Xdan Y, meskipun itu agak tidak biasa di GolfScript. Meninggalkan 1benar atau 0salah pada tumpukan.

C (52 karakter)

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

Uji kasus

Burlesque (6 karakter)

6 karakter dalam Burlesque: R@\/~[ (dengan asumsi x dan y ada di stack. Lihat di sini dalam aksi.)

C, 23:

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

menghasilkan * x

http://ideone.com/BpITZ

PHP, 90 karakter

<?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

Upaya pertama saya di golf kode ... harap saya tidak mempermalukan keluarga saya!

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]

Edit : ternyata Coffeescript lebih memaafkan daripada yang saya kira dengan spasi putih.

Terima kasih kepada res dan Peter Taylor untuk beberapa tips untuk membuatnya lebih ramping

C #, 70 113 107 90 karakter

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

Mathematica 19 17 27

LongestCommonSequencemengembalikan urutan terpanjang non-berdekatan dari dua string. (Jangan dikelirukan dengan LongestCommonSubsequence, yang mengembalikan urutan berdekatan paling lama.

Berikut ini memeriksa apakah urutan berdekatan terpanjang adalah yang pertama dari dua string. (Jadi, Anda harus memasukkan string yang lebih pendek diikuti oleh string yang lebih besar.)

LongestCommonSequence@##==#& 

Contohnya

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

Benar Benar Benar Salah

Tes kritis adalah yang ketiga, karena "anna" terkandung secara tidak berdampingan dalam "pisang".

Python 3.8 (pra-rilis) , 42 byte

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

Cobalah online!

Python 3.8 (pra-rilis) , 48 byte

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

Cobalah online!

Python 2 , 48 byte

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

Cobalah online!

Disalin dari jawaban Lynn ini . The >0dapat dihilangkan jika hanya truthy / falsey output OK.

Python 2 , 50 byte

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

Cobalah online!

Python 2 , 50 byte

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

Cobalah online!

C - 74 71 64

Ini tidak mengalahkan solusi Peter Taylor, tapi saya pikir ini cukup menyenangkan (plus, ini adalah program kerja yang lengkap, bukan hanya fungsi)

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];}

Dan ungolfed:

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;
}

Untuk mengujinya, Anda dapat melakukan sesuatu seperti:

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

Python, 66 62 59 58 karakter

Semacam solusi yang menyenangkan, pasti masalah yang rapi.

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

Ruby 32 30 28

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

Ini akan mengembalikan MatchDatainstance jika amerupakan hasil dari batau nilsebaliknya.

Versi lama yang menemukan substring alih-alih berikutnya

Ruby 15

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

Menggunakan String#[](str)metode yang mengembalikan strjika strmerupakan substring dari selfdan !!mengembalikan Booleanjika nilai yang dikembalikan dapat digunakan sebagai boolean (dan tidak perlu menjadi trueatau false) maka itu bisa hanya 13 karakter:

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

Ini akan kembali niljika abukan substring dari b.

SWI-Prolog, SICStus

Sublist predikat bawaan / 2 dari SICStus memeriksa apakah semua item dalam daftar pertama juga muncul di daftar kedua. Predikat ini juga tersedia di SWI-Prolog melalui pustaka kompatibilitas, yang dapat dimuat oleh kueri [library(dialect/sicstus/lists)]..

Contoh dijalankan:

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.

Hitungan byte secara teknis bisa 0, karena semua yang kita lakukan di sini adalah query, seperti bagaimana kita menjalankan sebuah program dan menyediakan input ke dalamnya.

PHP, 41 Bytes

mencetak 1 untuk true dan nothing for false

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

Jika hanya penyisipan dari kata 1 ke kata 2 dilakukan penghitungan adalah nol untuk kasus nyata

levenshtein

Cobalah online!

PHP, 57 Bytes

mencetak 1 untuk true dan 0 untuk false

Membuat Regex

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

Cobalah online!

Brachylog , 2 byte

⊆ᵈ

Cobalah online!

Seperti dengan jawaban ini, ⊆ adalah predikat bawaan yang menyatakan hubungan antara variabel input dan output, dan ᵈmerupakan predikat meta yang memodifikasinya untuk menyatakan bahwa hubungan yang sama antara elemen pertama dan kedua dari variabel input sebagai gantinya (dan menyatukan variabel output dengan elemen kedua tetapi karena ini adalah masalah keputusan yang tidak berakhir berarti di sini). X⊆Yadalah pernyataan bahwa X adalah kelanjutan dari Y, oleh karena itu begitu juga [X,Y]⊆ᵈ.

Predikat ini (yang tentu saja menghasilkan melalui keberhasilan atau kegagalan yang mencetak true.ataufalse. ketika dijalankan sebagai suatu program) mengambil input sebagai daftar dari dua string. Jika input sedikit lebih fleksibel ...

Brachylog , 1 byte

⊆

Cobalah online!

Mengambil string X sebagai variabel input dan string Y sebagai variabel output. Keluaran melalui keberhasilan atau kegagalan, seperti sebelumnya. Jika dijalankan sebagai program lengkap, X diberikan sebagai input dan Y disediakan sebagai argumen baris perintah pertama.

CoffeeScript 73

Inilah jawaban alternatif CoffeeScript, menggunakan regex bukannya rekursi:

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

Jika tumpukan jerami cocok dengan regex yang sangat rakus dibangun dari jarum, itu akan diganti dengan string kosong. Jika tumpukan jerami lebih pendek daripada yang dimulai, jarum adalah urutan.

Mengembalikan nilai false saat xdan ykeduanya merupakan string kosong. Pikirkan kita perlu filsuf untuk memberi tahu kita jika string kosong adalah hasil dari dirinya sendiri!

(Diposting sebagai jawaban yang terpisah dari jawaban saya sebelumnya karena rasanya cukup berbeda untuk membenarkannya).

PowerShell, 38

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

Tentu saja, solusi berbasis pencocokan regex atau pencocokan pola seperti itu memiliki masalah kinerja yang parah dengan string yang lebih panjang. Tapi karena sesak adalah kriteria ...

Semacam anti-solusi yang menghasilkan semua selanjutnya dari 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)

Penanganan string agak kurang dalam APL.

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

pemakaian:

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

Python 132

Mirip dengan Daniero. Bukan solusi termudah, tapi itu menyenangkan untuk dicoba. Saya baru mengenal Python, jadi saya yakin saya bisa membuatnya lebih pendek jika saya tahu sedikit lebih banyak.

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:])

Solusi rekursif sederhana. Pertama kali bermain golf, jadi setiap tips untuk mengurangi ini sangat dihargai :)

Diuji dengan yang berikut:

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

Terima kasih kepada @ lirtosiast untuk beberapa trik boolean yang pintar.

PHP, 75 65 64 byte

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

mengambil input dari argumen baris perintah; mencetak 1untuk string benar, kosong untuk false. Jalankan dengan -r.

penjelasan:

• strposkembali falsejika jarum $ctidak ada di tumpukan jerami $argv[2](setelah posisi $p),
  menyebabkan loop putus.
• strposjuga kembali falseuntuk jarum kosong, memutus loop pada akhir $argv[1].
• Jika $argv[1]merupakan kelanjutan dari $argv[2], $cakan kosong ketika loop putus.
• strposperlu @menekan Empty needleperingatan.

Swift, 27

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