Étant donné les chaînes X et Y, déterminez si X est une sous- séquence de Y. La chaîne vide est considérée comme une sous-séquence de chaque chaîne. (Par exemple, ''et 'anna'sont des sous-séquences de 'banana'.)

Contribution

• X, une chaîne alphanumérique sensible à la casse éventuellement vide
• Y, une chaîne alphanumérique sensible à la casse éventuellement vide

Sortie

• Vrai ou faux (ou équivalents), indiquant correctement si X est une sous-séquence de Y.

Exemples d'E / S

X      Y        output

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

Critères

• Le programme le plus court gagne, comme déterminé par le nombre d'octets de code source.

Exemples de programmes

• Plusieurs programmes qui pourraient être adaptés figurent dans cette publication connexe .

Perl 5 , 17 octets (+1?), Programme complet

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

Essayez-le en ligne!

Appelez avec le pdrapeau à l'interpréteur perl, comme dans perl -pe 's//.*/g;$_=<>=~$_'. Selon les règles de notation établies lorsque ce défi a été initialement publié , ce drapeau coûte un octet supplémentaire. Selon des règles plus récentes , AFAICT, il peut être gratuit.

Dans les deux cas, les chaînes d'entrée doivent être fournies sur des lignes séparées par des retours à la ligne sur stdin. La sortie (vers stdout) sera 1si la première chaîne d'entrée est une sous-chaîne de la seconde, ou rien du tout si ce n'est pas le cas.

Notez que les deux lignes d'entrée doivent avoir une nouvelle ligne à la fin, sinon le programme ne fonctionnera pas correctement. Alternativement, vous pouvez ajouter l' lindicateur de ligne de commande à l'invocation pour que perl supprime les sauts de ligne; selon les règles de notation en vigueur, cela peut ou non coûter un octet supplémentaire. Notez que l'utilisation de cet indicateur ajoutera également une nouvelle ligne à la sortie.

Version originale (extrait, 18 octets / caractères)

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

L'entrée est donnée dans les variables $xet le $yrésultat est la valeur de l'expression (dans un contexte scalaire). Notez que cela $xest modifié dans le processus. (Oui, je sais que l'utilisation $_au lieu de $xme permettrait d'enregistrer quatre caractères, mais le faire dans un extrait de code qui me semble un peu trop ringard.)

Comment ça marche?

La première partie $x=~s//.*/g,, insère la chaîne .*entre chaque caractère dans $x. La deuxième partie, $y=~$xtraite $xcomme une expression rationnelle et correspond $yà elle. Dans les expressions rationnelles Perl, .*correspond à zéro ou plusieurs caractères arbitraires, tandis que tous les caractères alphanumériques se correspondent facilement.

Ruby, 32 caractères

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

Cette solution renvoie nilsi xn'est pas une sous-séquence de yet un nombre dans le cas contraire (c'est-à-dire des équivalents rubis à falseet true). Exemples:

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

Merci à Hammar pour cette amélioration substantielle. C'est maintenant une fonction infixe, mais il ne semble pas y avoir de raison qu'elle ne le soit pas.

Manifestation:

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

Python (48 caractères)

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

Même approche que la réponse Ruby d'Howard. Dommage sur le besoin de Python d'importer le paquet regex et son "verbose" lambda. :-)

Python, 59 caractères

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

J'ai pensé que ma réponse serait mieux exprimée en Python.

Edit: Ajout des suggestions de res.

GolfScript (22 caractères)

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

Suppose que l'entrée est considérée comme deux variables prédéfinies Xet Y, bien que cela soit plutôt inhabituel dans GolfScript. Laisse 1pour vrai ou 0pour faux sur la pile.

C (52 caractères)

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

Cas de test

Burlesque (6 caractères)

6 caractères dans Burlesque: R@\/~[ (en supposant que x et y sont sur la pile. Voir ici en action.)

C, 23:

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

résultat en * x

http://ideone.com/BpITZ

PHP, 90 caractères

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

Ma première tentative de code golf ... j'espère que je n'ai pas honte à ma famille!

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 : il s'avère que Coffeescript est plus indulgent que je ne le pensais avec les espaces blancs.

Merci à res et Peter Taylor pour quelques conseils pour le rendre un peu plus élégant

C #, 70 113 107 90 caractères

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

LongestCommonSequencerenvoie la plus longue sous-séquence non contiguë de deux chaînes. (À ne pas confondre avec LongestCommonSubsequence, qui renvoie la sous-séquence contiguë la plus longue.

Ce qui suit vérifie si la sous-séquence contiguë la plus longue est la première des deux chaînes. (Vous devez donc entrer la chaîne la plus courte suivie de la plus grande.)

LongestCommonSequence@##==#& 

Exemples

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

Vrai Vrai Vrai Faux

Le test critique est le troisième, car "anna" est contenue non contiguë dans "banana".

Python 3.8 (version préliminaire) , 42 octets

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

Essayez-le en ligne!

Python 3.8 (pré-version) , 48 octets

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

Essayez-le en ligne!

Python 2 , 48 octets

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

Essayez-le en ligne!

Copié de cette réponse de Lynn . Le >0peut être omis si la sortie vérité / falsey est correcte.

Python 2 , 50 octets

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

Essayez-le en ligne!

Python 2 , 50 octets

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

Essayez-le en ligne!

C - 74 71 64

Cela ne bat pas la solution de Peter Taylor, mais je pense que c'est assez amusant (en plus, c'est un programme de travail complet, pas seulement une fonction)

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

Et non golfé:

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

Pour le tester, vous pouvez faire quelque chose comme:

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

Python, 66 62 59 58 caractères

Une sorte de solution amusante, certainement un problème soigné.

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

Rubis 32 30 28

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

Cela retournera l' MatchDatainstance si aest une sous-séquence de bou nilautrement.

Ancienne version qui trouve une sous-chaîne au lieu d'une sous-séquence

Rubis 15

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

En utilisant une String#[](str)méthode qui retourne strif strest une sous-chaîne de selfet !!pour retourner Booleansi la valeur retournée peut être utilisable en tant que booléen (et n'a pas besoin d'être trueou false), elle ne peut être que de 13 caractères:

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

Il retournera nilsi an'est pas une sous-chaîne de b.

SWI-Prolog, SICStus

La sous- liste de prédicats intégrée / 2 de SICStus vérifie si tous les éléments de la première liste apparaissent également dans la deuxième liste. Ce prédicat est également disponible dans SWI-Prolog via une bibliothèque de compatibilité, qui peut être chargée par la requête [library(dialect/sicstus/lists)]..

Exemple d'exécution:

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.

Le nombre d'octets peut être techniquement égal à 0, car tout ce que nous faisons ici est d'interroger, tout comme la façon dont nous exécutons un programme et lui fournissons une entrée.

PHP, 41 octets

imprime 1 pour vrai et rien pour faux

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

Si seules les insertions du mot 1 au mot 2 sont effectuées, le compte est nul pour les cas réels

levenshtein

Essayez-le en ligne!

PHP, 57 octets

imprime 1 pour vrai et 0 pour faux

Crée une expression régulière

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

Essayez-le en ligne!

Brachylog , 2 octets

⊆ᵈ

Essayez-le en ligne!

Comme avec cette réponse, ⊆ est un prédicat intégré qui déclare une relation entre les variables d'entrée et de sortie, et ᵈest un méta-prédicat qui le modifie pour déclarer cette même relation entre les premier et deuxième éléments de la variable d'entrée à la place (et unifier la variable de sortie avec le deuxième élément mais comme c'est un problème de décision qui ne finit pas par avoir d'importance ici). X⊆Yest une affirmation que X est une sous-séquence de Y, donc c'est le cas [X,Y]⊆ᵈ.

Ce prédicat (qui bien sûr sort par le succès ou l'échec qui s'imprime true.ou false.lorsqu'il est exécuté en tant que programme) prend l'entrée comme une liste de deux chaînes. Si l'entrée est un peu plus flexible ...

Brachylog , 1 octet

⊆

Essayez-le en ligne!

Prend la chaîne X comme variable d'entrée et la chaîne Y comme variable de sortie. Sorties par succès ou échec, comme précédemment. S'il est exécuté en tant que programme complet, X est fourni comme entrée et Y est fourni comme premier argument de ligne de commande.

CoffeeScript 73

Voici une réponse alternative à CoffeeScript, en utilisant des expressions rationnelles au lieu de la récursivité:

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

Si la botte de foin correspond à une expression rationnelle très gourmande construite à partir de l'aiguille, elle sera remplacée par une chaîne vide. Si la botte de foin est plus courte qu'elle n'a commencé, l'aiguille était une sous-séquence.

Renvoie false lorsque xet ysont deux chaînes vides. Pensez que nous avons besoin d'un philosophe pour nous dire si une chaîne vide est une sous-séquence d'elle-même!

(Publié comme une réponse distincte de ma précédente car elle semble suffisamment différente pour la justifier).

PowerShell, 38

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

Bien sûr, une telle solution basée sur l'expression rationnelle ou la correspondance de modèles présente de graves problèmes de performances avec des chaînes plus longues. Mais comme la brièveté est le critère ...

Une sorte d'anti-solution générant toutes les sous-séquences 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)

La gestion des chaînes fait un peu défaut dans APL.

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

usage:

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

Python 132

Similaire à Daniero. Ce n'était pas la solution la plus simple, mais c'était amusant à essayer. Je suis nouveau sur Python, donc je suis sûr que je pourrais le raccourcir si j'en savais un peu plus.

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

Solution récursive simple. Golf pour la première fois, donc tous les conseils pour le réduire sont très appréciés :)

Testé avec les éléments suivants:

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

Merci à @lirtosiast pour quelques astuces booléennes intelligentes.

PHP, 75 65 64 octets

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

prend l'entrée des arguments de la ligne de commande; affiche 1pour vrai, chaîne vide pour faux. Courez avec -r.

explication:

• strposrevient falsesi l'aiguille $cn'est pas dans la botte de foin $argv[2](après la position $p),
  provoquant la rupture de la boucle.
• strposrevient également falsepour une aiguille vide, rompant la boucle à la fin de $argv[1].
• Si $argv[1]est une sous-séquence de $argv[2], $csera vide lorsque la boucle se cassera.
• strposdoit @supprimer l' Empty needleavertissement.

Swift, 27

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