Trouver la plus longue sous-chaîne de départ commune dans un ensemble de chaînes de caractères.

Question

Il s'agit de relever le défi de trouver la solution la plus élégante en JavaScript, Ruby ou autre à un problème relativement trivial.

Ce problème est un cas plus spécifique de la Problème de la plus longue sous-chaîne commune . Je dois seulement trouver le plus long point commun démarrage sous-chaîne dans un tableau. Cela simplifie grandement le problème.

Par exemple, la plus longue sous-chaîne dans [interspecies, interstelar, interstate] est "inters". Cependant, je n'ai pas besoin de trouver "ific" dans [specifics, terrific] .

J'ai résolu le problème en codant rapidement une solution en JavaScript dans le cadre de mon projet de réponse à propos de la saisie par tabulation de type shell ( page de test ici ). Voici cette solution, légèrement modifiée :

function common_substring(data) {
  var i, ch, memo, idx = 0
  do {
    memo = null
    for (i=0; i < data.length; i++) {
      ch = data[i].charAt(idx)
      if (!ch) break
      if (!memo) memo = ch
      else if (ch != memo) break
    }
  } while (i == data.length && idx < data.length && ++idx)

  return (data[0] || '').slice(0, idx)
}

Ce site Le code est disponible dans ce Gist ainsi qu'une solution similaire en Ruby. Vous pouvez cloner le gist comme un repo git pour l'essayer :

$ git clone git://gist.github.com/257891.git substring-challenge

Je ne suis pas très satisfait de ces solutions. J'ai le sentiment qu'elles pourraient être résolues avec plus d'élégance et moins de complexité d'exécution - c'est pourquoi je publie ce défi.

Je vais accepter comme réponse la solution que je trouve la plus élégante ou la plus concise. Voici par exemple un hack Ruby un peu fou que j'ai inventé : définir la fonction & sur une chaîne :

# works with Ruby 1.8.7 and above
class String
  def &(other)
    difference = other.to_str.each_char.with_index.find { |ch, idx|
      self[idx].nil? or ch != self[idx].chr
    }
    difference ? self[0, difference.last] : self
  end
end

class Array
  def common_substring
    self.inject(nil) { |memo, str| memo.nil? ? str : memo & str }.to_s
  end
end

Les solutions en JavaScript ou Ruby sont préférées, mais vous pouvez présenter une solution intelligente dans d'autres langages tant que vous expliquez ce qui se passe. Seulement le code de la bibliothèque standard s'il vous plaît.

Mise à jour : mes solutions préférées

J'ai choisi le Solution de triage JavaScript par kennebec comme la "réponse" parce qu'elle m'a paru à la fois inattendue et géniale. Si nous ne tenons pas compte de la complexité du tri réel (imaginons qu'il soit optimisé à l'infini par l'implémentation du langage), la complexité de la solution consiste simplement à comparer deux chaînes de caractères.

D'autres solutions intéressantes :

• "avidité de regex" par FM prend une minute ou deux à saisir, mais ensuite l'élégance de la chose vous frappe. Yehuda Katz a également fait une solution regex mais c'est plus complexe
• commonprefix en Python - Roberto Bonvallet a utilisé une fonction conçue pour gérer les chemins du système de fichiers pour résoudre ce problème.
• Haskell one-liner est courte comme si elle était comprimée, et belle
• le langage simple et direct de Ruby

Merci de votre participation ! Comme vous pouvez le voir dans les commentaires, j'ai beaucoup appris (même sur Ruby).

Answer 1

C'est une question de goût, mais voici une version simple en javascript : Il trie le tableau, et ensuite regarde juste le premier et le dernier élément.

function sharedStart(array){
    var A= array.slice(0).sort(), 
    word1= A[0], word2= A[A.length-1], 
    L= word1.length, i= 0;
    while(i<L && word1.charAt(i)=== word2.charAt(i)) i++;
    return word1.substring(0, i);
}

DEMOS

sharedStart(['interspecies', 'interstelar', 'interstate'])  //=> 'inters'
sharedStart(['throne', 'throne'])                           //=> 'throne'
sharedStart(['throne', 'dungeon'])                          //=> ''
sharedStart(['cheese'])                                     //=> 'cheese'
sharedStart([])                                             //=> ''
sharedStart(['prefix', 'suffix'])                           //=> ''

Answer 2

En Python :

>>> from os.path import commonprefix
>>> commonprefix('interspecies interstelar interstate'.split())
'inters'

Answer 3

Ruby one-liner :

l=strings.inject{|l,s| l=l.chop while l!=s[0...l.length];l}

Answer 4

Il suffit de parcourir toutes les chaînes jusqu'à ce qu'elles diffèrent, puis de prendre la sous-chaîne jusqu'à ce point.

Pseudocode :

loop for i upfrom 0
     while all strings[i] are equal
     finally return substring[0..i]

Common Lisp :

(defun longest-common-starting-substring (&rest strings)
  (loop for i from 0 below (apply #'min (mapcar #'length strings))
     while (apply #'char=
                  (mapcar (lambda (string) (aref string i))
                          strings))
     finally (return (subseq (first strings) 0 i))))

Answer 5

Ma phrase en Haskell :

import Data.List

commonPre :: [String] -> String
commonPre = map head . takeWhile (\(x:xs)-> all (==x) xs) . transpose

EDIT : barkmadley a donné une bonne explication du code ci-dessous. J'ajouterais aussi que haskell utilise l'évaluation paresseuse, donc nous pouvons être paresseux sur l'utilisation de transpose il ne transposera nos listes que dans la mesure nécessaire pour trouver la fin du préfixe commun.