Dans quelle mesure mes cordes sont-elles compatibles?

12

introduction

Considérons deux chaînes A et B de même longueur L et un entier K ≥ 0 . Aux fins de ce défi, nous disons que les chaînes sont compatibles K , s'il existe une chaîne C de longueur K telle que A est une sous-chaîne contiguë de la concaténation BCB . Notez que A est une sous-chaîne de BAB , donc A et B sont toujours compatibles avec L (mais peuvent également être compatibles avec K pour certains autres K <L ).

Contribution

Vos entrées sont deux chaînes de la même longueur positive, composées de lettres ASCII majuscules et minuscules.

Production

Votre sortie doit être le plus petit entier non négatif K tel que les entrées soient compatibles K.

Exemple

Considérez les entrées

A = HHHHHH
B = HHttHH

Ils ne sont pas compatibles 0, car A n'est pas une sous-chaîne de HHttHHHHttHH. Ils ne sont pas non plus compatibles 1, car A n'est pas une sous-chaîne, HHttHH#HHttHHquelle que soit la lettre placée sur le #. Cependant, A est une sous-chaîne de HHttHHHHHHttHH, où C est la chaîne de deux lettres HH. Ainsi, les entrées sont compatibles 2 et la sortie correcte l'est 2.

Règles et notation

Vous pouvez écrire un programme complet ou une fonction. Le nombre d'octets le plus bas gagne et les failles standard sont interdites.

Cas de test

La condition de compatibilité est symétrique, donc l'échange des deux entrées ne devrait pas changer la sortie.

E G -> 1
E E -> 0
aB Bc -> 1
YY tY -> 1
abcd bcda -> 0
abcXd bxcda -> 4
Hello Hello -> 0
Hello olHel -> 1
aBaXYa aXYaBa -> 1
aXYaBa aBaXYa -> 1
HHHHHH HHttHH -> 2
abcdab cdabcd -> 2
XRRXXXXR XRXXRXXR -> 4
evveeetev tetevevev -> 7
vzzvzJvJJz vJJvzJJvJz -> 10
JJfcfJJcfJfb JcfJfbbJJJfJ -> 5
GhhaaHHbbhGGH HHaaHHbbGGGhh -> 9
OyDGqyDGDOGOGyG yDGqOGqDyyyyOyD -> 12
ffKKBBpGfGKpfGpbKb fGpbKbpBBBffbbbffK -> 9
UZuPPZuPdVdtuDdDiuddUPtUidtVVV dtUPtUidtVVVtDZbZZPuiUZuPPZuPd -> 21

Classement

Voici un extrait de pile pour générer un classement et une liste des gagnants par langue. Pour vous assurer que votre réponse s'affiche, commencez-la par un en-tête du formulaire

## Language, N bytes

Vous pouvez conserver les anciens scores dans l'en-tête en utilisant les balises barrées: <s>57</s>apparaîtra comme 57 .

Afficher l'extrait de code

code-golf string Zgarb
la source

Réponses:

8

Pyth, 16

lhf}QjT,vzvz+k.:

Trouvez la sous-chaîne la plus courte de A qui, lorsqu'elle est insérée entre deux copies de B, génère une chaîne qui contient A.

Cela pourrait être deux octets plus court si la deuxième ligne n'avait pas de guillemets, mais cela vous semble bizarre?

Suite de tests

FryAmTheEggman
la source
4

Python 3, 155 168 157 octets

Le total est la longueur de A. Comparez le début de Ala fin Bet soustrayez-le du total. Comparez le début de Bla fin Aet soustrayez-le du total. Renvoie la valeur absolue de total sauf si total est égal à la longueur, auquel cas retourne 0.

def f(A,B):
    T=L=len(A)
    C=D=1
    for i in range(L,0,-1):
        if A[:i]==B[-i:]and C:
            T,C=T-i,0
        if A[-i:]==B[:i]and D:
            T,D=T-i,0
    return (0,abs(T))[T!=-L]

Modifier: gérer le f("abcdab","cdabcd")==2cas

Non linéaire
la source
3
Malheureusement, cela ne fonctionne pas, f("abcdab", "cdabcd")ce qui devrait être 2.
Neil
@Neil Bonne prise. Je vais ajouter cela aux cas de test.
Zgarb
1
C'était inattendu. ( Global Twitch Emotes )
F. George
@ mEQ5aNLrK3lqs3kfSa5HbvsTWe0nIu Je regardais l'image et je pensais 'C'est une idée astucieuse de débogueur pour utiliser des emojis, mais je ne vois pas de bug ...'. Je pense que l'add-on ferait des ravages sur ce site.
NonlinearFruit
3

Rétine , 49 octets

.*?(?<=^(?=(.*)(?<4-3>.)*(.*) \2.*\1$)(.)*).+
$#4

Essayez-le en ligne! (Légèrement modifié pour exécuter tous les tests en même temps.)

L'astuce est que nous devons revenir en arrière sur la partie Aque nous ne trouvons pasB , et jusqu'à présent, je n'ai pas trouvé de moyen de le faire sans des contournements plutôt ennuyeux et des groupes d'équilibrage.

Martin Ender
la source
3

Jolf, 40 octets

Wά)Ζ0W<ζli)? h++i]Iζ+ζniIoά0nΖhζ}onhn}wn

Essayez!

Je suis assez nouveau pour Jolf, j'ai beaucoup appris en le découvrant. Semble un peu gênant, pourrait encore probablement être creusé plus loin. Même supprimé 2 octets lors de l'écriture de cette explication.

Explication:

  Wά)                                      While ά (initialized to 16)
     Ζ0                                    Set ζ to 0
       W<ζli)                              While ζ < length(A)
             ? h++i]Iζ+ζniIoά0n            Set ά to 0 if (A + a substring from B of length n + A) contains B
                               Ζhζ         Increment ζ
                                  }onhn    Increment n (initialize to 0
                                       }wn Decrement n and print
gonfle
la source
Je n'ai pas vraiment essayé, et cela peut être une solution optimale, mais je suggère d'essayer de cartographier les plages. ( s0zlivous donnera un tableau [0 ... longueur i] si vous souhaitez essayer cette approche.)
Conor O'Brien
@ Cᴏɴᴏʀ O'Bʀɪᴇɴ Hmm, je vais y jeter un coup d'œil ... y a-t-il également une commande if que j'ai rejetée en parcourant la documentation / source ou est-ce la seule option? avec un troisième argument non pertinent?
gonfle
?est le plus proche d'un s'il y en a à Jolf. C'est comme un ternaire si. ?ABCs returns B` si a est vrai, et Csinon.
Conor O'Brien
2

JavaScript (ES6), 110 octets

(a,b)=>{for(i=0;;i++)for(j=i;j<=a.length;j++)if(b.startsWith(a.slice(j))&&b.endsWith(a.slice(0,j-i)))return i}

Fonctionne en coupant des morceaux toujours plus longs du milieu ajusqu'à ce qu'ils correspondent aux deux extrémités de b. La boucle n'est pas infinie car elle s'arrêtera le ou avant i == a.length.

Neil
la source