Dadas las cadenas X e Y, determine si X es una subsecuencia de Y. La cadena vacía se considera una subsecuencia de cada cadena. (Por ejemplo, ''y 'anna'son subsecuencias de 'banana'.)

Entrada

• X, una cadena alfanumérica entre mayúsculas y minúsculas posiblemente vacía
• Y, una cadena alfanumérica sensible a mayúsculas y minúsculas posiblemente vacía

Salida

• Verdadero o Falso (o equivalentes), indicando correctamente si X es una subsecuencia de Y.

Ejemplos de E / S

X      Y        output

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

Criterios

• El programa más corto gana, según lo determinado por el número de bytes del código fuente.

Programas de ejemplo

• Varios programas que podrían adaptarse están en esta publicación relacionada .

Perl 5 , 17 bytes (+1?), Programa completo

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

Pruébalo en línea!

Invoque con la pbandera al intérprete perl, como en perl -pe 's//.*/g;$_=<>=~$_'. Según las reglas de puntuación establecidas cuando este desafío se publicó originalmente , esta bandera cuesta un byte adicional. Bajo reglas más recientes , AFAICT, puede ser gratis.

De cualquier manera, las cadenas de entrada deben suministrarse en líneas separadas terminadas en nueva línea en stdin. La salida (a stdout) será 1si la primera cadena de entrada es una subcadena de la segunda, o nada en absoluto si no lo es.

Tenga en cuenta que ambas líneas de entrada deben tener una nueva línea al final, o el programa no funcionará correctamente. Alternativamente, puede agregar el lindicador de línea de comando a la invocación para hacer que Perl elimine las nuevas líneas; dependiendo de las reglas de puntuación vigentes, esto puede costar o no un byte adicional. Tenga en cuenta que el uso de este indicador también agregará una nueva línea a la salida.

Versión original (fragmento, 18 bytes / caracteres)

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

La entrada se da en las variables $xy $y, el resultado es el valor de la expresión (en contexto escalar). Tenga en cuenta que $xse modifica en el proceso. (Sí, sé que usar en $_lugar de $xpermitirme guardar cuatro caracteres, pero hacerlo en un fragmento que me parece un poco cursi).

¿Como funciona?

La primera parte, $x=~s//.*/ginserta la cadena .*entre cada carácter en $x. La segunda parte, $y=~$xtrata $xcomo una expresión regular y coincide $ycon ella. En expresiones regulares de Perl, .*coincide con cero o más caracteres arbitrarios, mientras que todos los caracteres alfanuméricos coinciden convenientemente.

Ruby, 32 caracteres.

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

Esta solución devuelve nilsi xno es una subsecuencia de yy un número de lo contrario (es decir, equivalentes de rubí a falsey true). Ejemplos:

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

Gracias a Hammar por la mejora sustancial. Ahora es una función infija, pero parece que no hay ninguna razón por la cual no debería.

Demostración:

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

Python (48 caracteres)

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

El mismo enfoque que la respuesta de Howard Ruby. Lástima la necesidad de Python de importar el paquete regex y su "detallado" lambda. :-)

Python, 59 caracteres

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

Pensé que mi respuesta se expresaría mejor en Python.

Editar: Se agregaron sugerencias de res.

GolfScript (22 caracteres)

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

Asume que la entrada se toma como dos variables predefinidas Xy Y, aunque eso es bastante inusual en GolfScript. Deja 1para verdadero o 0para falso en la pila.

C (52 caracteres)

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

Casos de prueba

Burlesque (6 caracteres)

6 caracteres en burlesco: R@\/~[ (suponiendo que x e y están en la pila. Ver aquí en acción).

C, 23:

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

resultar en * x

http://ideone.com/BpITZ

PHP, 90 caracteres

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

Mi primer intento de golf de código ... ¡espero no avergonzar a mi familia!

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]

Editar : resulta que Coffeescript es más indulgente de lo que pensaba con espacios en blanco.

Gracias a res y Peter Taylor por algunos consejos para hacerlo un poco más elegante

C #, 70 113 107 90 caracteres

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

LongestCommonSequencedevuelve la subsecuencia no contigua más larga de dos cadenas. (No debe confundirse con LongestCommonSubsequence, lo que devuelve la subsecuencia contigua más larga.

Lo siguiente verifica si la subsecuencia contigua más larga es la primera de las dos cadenas. (Por lo tanto, debe ingresar la cadena más corta seguida de la cadena más grande).

LongestCommonSequence@##==#& 

Ejemplos

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

Verdadero Verdadero Verdadero Falso

La prueba crítica es la tercera, porque "anna" está contenida de manera no contigua en "banana".

Python 3.8 (prelanzamiento) , 42 bytes

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

Pruébalo en línea!

Python 3.8 (prelanzamiento) , 48 bytes

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

Pruébalo en línea!

Python 2 , 48 bytes

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

Pruébalo en línea!

Copiado de esta respuesta de Lynn . Se >0puede omitir si solo la salida truey / falsey está bien.

Python 2 , 50 bytes

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

Pruébalo en línea!

Python 2 , 50 bytes

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

Pruébalo en línea!

C - 74 71 64

Esto no supera la solución de Peter Taylor, pero creo que es bastante divertido (además, este es un programa de trabajo completo, no solo una función)

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

Y sin golfos:

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

Para probarlo puedes hacer algo como:

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

Pitón, 66 62 59 58 caracteres

Una especie de solución divertida, definitivamente un buen problema.

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

Rubí 32 30 28

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

Esto devolverá la MatchDatainstancia si aes subsecuencia de bo nilno.

Versión antigua que encuentra subcadena en lugar de subsecuencia

Rubí 15

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

Usando el String#[](str)método que devuelve strif stres una subcadena de selfy !!para devolver Booleansi el valor devuelto puede ser utilizable como boolean (y no necesita ser trueo false), entonces puede ser solo 13 caracteres:

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

Volverá nilsi ano es una subcadena de b.

SWI-Prolog, SICStus

El predicado incorporado sublist / 2 de SICStus verifica si todos los elementos en la primera lista también aparecen en la segunda lista. Este predicado también está disponible en SWI-Prolog a través de la biblioteca de compatibilidad, que la consulta puede cargar [library(dialect/sicstus/lists)]..

Ejecución de muestra:

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.

El recuento de bytes puede ser técnicamente 0, ya que todo lo que estamos haciendo aquí es realizar consultas, de forma muy similar a cómo ejecutamos un programa y le proporcionamos información.

PHP, 41 bytes

imprime 1 para verdadero y nada para falso

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

Si solo se hicieron inserciones de la palabra 1 a la palabra 2, el recuento es cero para los casos verdaderos

levenshtein

Pruébalo en línea!

PHP, 57 bytes

imprime 1 para verdadero y 0 para falso

Crea una expresión regular

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

Pruébalo en línea!

Brachylog , 2 bytes

⊆ᵈ

Pruébalo en línea!

Al igual que con esta respuesta, ⊆ es un predicado incorporado que declara una relación entre las variables de entrada y salida, y ᵈes un meta-predicado que lo modifica para declarar esa misma relación entre el primer y el segundo elemento de la variable de entrada (y unificar la variable de salida con el segundo elemento, pero como este es un problema de decisión que no termina importando aquí). X⊆Yes una afirmación de que X es una subsecuencia de Y, por lo tanto, también lo es [X,Y]⊆ᵈ.

Este predicado (que, por supuesto, se genera a través del éxito o el fracaso que se imprime true.o false.cuando se ejecuta como un programa) toma la entrada como una lista de dos cadenas. Si la entrada es un poco más flexible ...

Brachylog , 1 byte

⊆

Pruébalo en línea!

Toma la cadena X como la variable de entrada y la cadena Y como la variable de salida. Salidas por éxito o fracaso, como antes. Si se ejecuta como un programa completo, X se proporciona como entrada e Y se proporciona como primer argumento de línea de comando.

CoffeeScript 73

Aquí hay una respuesta alternativa de CoffeeScript, utilizando expresiones regulares en lugar de recursividad:

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

Si el pajar coincide con una expresión regular muy codiciosa construida a partir de la aguja, se reemplazará con una cadena vacía. Si el pajar es más corto de lo que comenzó, la aguja era una subsecuencia.

Devuelve falso cuando xy yson ambas cadenas vacías. ¡Cree que necesitamos un filósofo que nos diga si una cadena vacía es una subsecuencia de sí misma!

(Publicado como una respuesta separada de mi anterior porque se siente lo suficientemente diferente como para justificarlo).

PowerShell, 38

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

Por supuesto, cualquier solución basada en coincidencia de expresiones o patrones tiene graves problemas de rendimiento con cadenas más largas. Pero como la brevedad es el criterio ...

Una especie de anti-solución que genera todas las subsecuencias de 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)

El manejo de cadenas es un poco escaso en APL.

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

uso:

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

Python 132

Similar al de Daniero. No es la solución más fácil, pero fue divertido intentarlo. Soy nuevo en Python, así que estoy seguro de que podría acortarlo si supiera un poco más.

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

Pitón ( 75 52)

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

Solución recursiva simple. Golf por primera vez, por lo que cualquier consejo para reducir esto es muy apreciado :)

Probado con lo siguiente:

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

Gracias a @lirtosiast por algunos ingeniosos trucos booleanos.

PHP, 75 65 64 bytes

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

toma datos de los argumentos de la línea de comandos; imprime 1para verdadero, cadena vacía para falso. Corre con -r.

explicación:

• strposregresa falsesi la aguja $cno está en el pajar $argv[2](después de la posición $p),
  haciendo que el lazo se rompa.
• strpostambién regresa falsepor una aguja vacía, rompiendo el lazo al final de $argv[1].
• Si $argv[1]es una subsecuencia de $argv[2], $cestará vacía cuando se rompa el bucle.
• strposnecesita @suprimir la Empty needleadvertencia.

Swift, 27

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