Znajdź najdłuższy wspólny podłańcuch początkowy w zbiorze łańcuchów [zamknięty]

W Pythonie:

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

Ruby one-liner:

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

Mój Haskell one-liner:

import Data.List

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

EDIT: barkmadley podał dobre wyjaśnienie poniższego kodu. Dodam również, że haskell używa leniwej oceny, więc możemy być leniwi w kwestii użycia transpose; transponuje nasze listy tylko tak daleko, jak to konieczne, aby znaleźć koniec wspólnego prefiksu.

Musisz po prostu przejść wszystkie ciągi, aż się różnią, a następnie wziąć podciąg aż do tego punktu.

Pseudokod:

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

Yet another way to do it: use regex greed.

words = %w(interspecies interstelar interstate)
j = '='
str = ['', *words].join(j)
re = "[^#{j}]*"

str =~ /\A
    (?: #{j} ( #{re} ) #{re} )
    (?: #{j}    \1     #{re} )*
\z/x

p $1

I jednoliterowy, dzięki uprzejmości mislava (50 znaków):

p ARGV.join(' ').match(/^(\w*)\w*(?: \1\w*)*$/)[1]

W Pythonie nie użyłbym niczego poza istniejącą commonprefix funkcją, którą pokazałem w innej odpowiedzi, ale nie mogłem pomóc w odkryciu koła :P. To jest moje podejście oparte na iteratorze:

>>> a = 'interspecies interstelar interstate'.split()
>>>
>>> from itertools import takewhile, chain, izip as zip, imap as map
>>> ''.join(chain(*takewhile(lambda s: len(s) == 1, map(set, zip(*a)))))
'inters'

Edit: Wyjaśnienie jak to działa.

zip generuje krotki elementów biorących po jednym elemencie a na raz:

In [6]: list(zip(*a))  # here I use list() to expand the iterator
Out[6]:
[('i', 'i', 'i'),
 ('n', 'n', 'n'),
 ('t', 't', 't'),
 ('e', 'e', 'e'),
 ('r', 'r', 'r'),
 ('s', 's', 's'),
 ('p', 't', 't'),
 ('e', 'e', 'a'),
 ('c', 'l', 't'),
 ('i', 'a', 'e')]

Mapując set nad tymi przedmiotami, otrzymuję serię unikalnych liter:

In [7]: list(map(set, _))  # _ means the result of the last statement above
Out[7]:
[set(['i']),
 set(['n']),
 set(['t']),
 set(['e']),
 set(['r']),
 set(['s']),
 set(['p', 't']),
 set(['a', 'e']),
 set(['c', 'l', 't']),
 set(['a', 'e', 'i'])]

takewhile(predicate, items) bierze z tego elementy, podczas gdy predykat jest prawdziwy; w tym konkretnym przypadku, gdy set s mają jeden element, tzn. wszystkie słowa mają tę samą literę w tej pozycji:

In [8]: list(takewhile(lambda s: len(s) == 1, _))
Out[8]:
[set(['i']),
 set(['n']), 
 set(['t']), 
 set(['e']), 
 set(['r']), 
 set(['s'])]

W tym momencie mamy iterowalne zbiory, z których każdy zawiera jedną literę przedrostka, którego szukamy. Aby skonstruować łańcuch, możemy chain je w pojedynczy iterable, z którego otrzymujemy litery join do końcowego ciągu.

Magia używania iteratorów polega na tym, że wszystkie elementy są generowane na żądanie, więc gdy takewhile przestaje prosząc o przedmioty, zamek zatrzymuje się w tym momencie i nie wykonuje się niepotrzebnej pracy. Każde wywołanie funkcji w moim jednowierszu ma implicit for i implicit break.

Nie jest to prawdopodobnie najbardziej zwięzłe rozwiązanie (zależy, czy masz już do tego bibliotekę), ale jedną z eleganckich metod jest użycie trie. Używam tries do implementacji wypełniania tabulatorów w moim interpreterze Scheme:

Http://github.com/jcoglan/heist/blob/master/lib/trie.rb

Na przykład:

tree = Trie.new
%w[interspecies interstelar interstate].each { |s| tree[s] = true }
tree.longest_prefix('')
#=> "inters"

Używam ich również do dopasowywania nazw kanałów z symbolami wildcards dla protokołu Bayeux; zobacz te:

Http://github.com/jcoglan/faye/blob/master/client/channel.js

Http://github.com/jcoglan/faye/blob/master/lib/faye/channel.rb

Dla Zabawy, oto wersja napisana w (SWI-)prologu:

common_pre([[C|Cs]|Ss], [C|Res]) :-
  maplist(head_tail(C), [[C|Cs]|Ss], RemSs), !,
  common_pre(RemSs, Res).
common_pre(_, []).

head_tail(H, [H|T], T).

Running:

?- S=["interspecies", "interstelar", "interstate"], common_pre(S, CP), string_to_list(CPString, CP).

Daje:

CP = [105, 110, 116, 101, 114, 115],
CPString = "inters".

Wyjaśnienie:

(SWI-)PROLOG traktuje łańcuchy jako listy kodów znaków (liczb). Wszystkie predykat common_pre/2 robi to rekurencyjnie pattern-match, aby wybrać pierwszy kod (C) z nagłówka pierwszej listy (string, [C|Cs]) na liście wszystkich list( all strings, [[C|Cs]|Ss]) i dodaje pasujący kod C do wyniku iff jest wspólna dla wszystkich (pozostałych) głowic wszystkich list (łańcuchów), w przeciwnym razie kończy się.

A javascript version based on @ Svante ' s algorithm :

function commonSubstring(words){
    var iChar, iWord,
        refWord = words[0],
        lRefWord = refWord.length,
        lWords = words.length;
    for (iChar = 0; iChar < lRefWord; iChar += 1) {
        for (iWord = 1; iWord < lWords; iWord += 1) {
            if (refWord[iChar] !== words[iWord][iChar]) {
                return refWord.substring(0, iChar);
            }
        }
    }
    return refWord;
}

Łączenie odpowiedzi przez kennebec, Florian F i jberryman daje następujący jednoliniowy Haskell:

commonPrefix l = map fst . takeWhile (uncurry (==)) $ zip (minimum l) (maximum l)

Z Control.Arrow można uzyskać formę bez punktów:

commonPrefix = map fst . takeWhile (uncurry (==)) . uncurry zip . (minimum &&& maximum)

Python 2.6 (r26:66714, Oct  4 2008, 02:48:43) 

>>> a = ['interspecies', 'interstelar', 'interstate']

>>> print a[0][:max(
        [i for i in range(min(map(len, a))) 
            if len(set(map(lambda e: e[i], a))) == 1]
        ) + 1]

inters

• i for i in range(min(map(len, a))), Liczba maksymalnych wyszukiwań nie może być większa niż długość najkrótszego ciągu; w tym przykładzie można by to oszacować na [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

• len(set(map(lambda e: e[i], a))), 1) tworzy tablicę i-thdla każdego ciągu znaków na liście; 2) tworzy z niej zbiór; 3) określa rozmiar zbioru

• [i for i in range(min(map(len, a))) if len(set(map(lambda e: e[i], a))) == 1], zawierać tylko znaki, dla których rozmiar zestawu wynosi 1 (Wszystkie znaki w tej pozycji były takie same ..); tutaj oceniłoby to [0, 1, 2, 3, 4, 5]

• Na koniec weź max, Dodaj jeden i pobierz podłańcuch ...

Uwaga: powyższe nie działa dla a = ['intersyate', 'intersxate', 'interstate', 'intersrate'], ale to:

 >>> index = len(
         filter(lambda l: l[0] == l[1], 
             [ x for x in enumerate(
                 [i for i in range(min(map(len, a))) 
                     if len(set(map(lambda e: e[i], a))) == 1]
         )]))
 >>> a[0][:index]
 inters

Nie wydaje się to skomplikowane, jeśli nie martwisz się o najwyższą wydajność:]}

def common_substring(data)
  data.inject { |m, s| s[0,(0..m.length).find { |i| m[i] != s[i] }.to_i] }
end

Jedną z przydatnych cech inject jest możliwość wstępnego zalania pierwszego elementu tablicy. Pozwala to uniknąć czeku Nil memo.

puts common_substring(%w[ interspecies interstelar interstate ]).inspect
# => "inters"
puts common_substring(%w[ feet feel feeble ]).inspect
# => "fee"
puts common_substring(%w[ fine firkin fail ]).inspect
# => "f"
puts common_substring(%w[ alpha bravo charlie ]).inspect
# => ""
puts common_substring(%w[ fork ]).inspect
# => "fork"
puts common_substring(%w[ fork forks ]).inspect
# => "fork"

Update: Jeśli golf jest tutaj grą, to 67 znaków:

def f(d)d.inject{|m,s|s[0,(0..m.size).find{|i|m[i]!=s[i]}.to_i]}end

Ten jest bardzo podobny do rozwiązania Roberto Bonvalleta, z wyjątkiem ruby.

chars = %w[interspecies interstelar interstate].map {|w| w.split('') }
chars[0].zip(*chars[1..-1]).map { |c| c.uniq }.take_while { |c| c.size == 1 }.join

Pierwsza linia zastępuje każde słowo tablicą znaków. Następnie używam zip do tworzenia tej struktury danych:

[["i", "i", "i"], ["n", "n", "n"], ["t", "t", "t"], ...

map i uniq zmniejsz to do [["i"],["n"],["t"], ...

take_while ściąga znaki z tablicy, dopóki nie znajdzie takiego, w którym rozmiar nie jest jeden (co oznacza, że nie wszystkie znaki były takie same). Wreszcie, ja [7]} je z powrotem razem.

Przyjęte rozwiązanie jest złamane (na przykład zwraca {[1] } dla ciągów takich jak ['a', 'ba']). Poprawka jest bardzo prosta, dosłownie trzeba zmienić tylko 3 znaki (z indexOf(tem1) == -1 na indexOf(tem1) != 0) i funkcja będzie działać zgodnie z oczekiwaniami.

Niestety, kiedy próbowałem edytować odpowiedź, aby naprawić literówkę, powiedział mi, że "edycje muszą mieć co najmniej 6 znaków". I mógłbym zmienić więcej niż te 3 znaki, poprawiając nazewnictwo i czytelność, ale to wydaje się trochę zbyt much.

Poniżej znajduje się poprawiona (przynajmniej z mojego punktu widzenia) wersja rozwiązania kennebec:

function commonPrefix(words) {
  max_word = words.reduce(function(a, b) { return a > b ? a : b });
  prefix   = words.reduce(function(a, b) { return a > b ? b : a }); // min word

  while(max_word.indexOf(prefix) != 0) {
    prefix = prefix.slice(0, -1);
  }

  return prefix;
}

(on jsFiddle )

Zauważ, że używa metody reduce (JavaScript 1.8) w celu znalezienia alfanumerycznego max / min zamiast sortowania tablicy, a następnie pobierania pierwszego i ostatniego jej elementów.

Czytając te odpowiedzi z całym fantazyjnym programowaniem funkcyjnym, sortowaniem i wyrażeniami regularnymi i tym podobne, pomyślałem: co jest nie tak z odrobiną C? Oto mały, głupkowato wyglądający program.

#include <stdio.h>

int main (int argc, char *argv[])
{
  int i = -1, j, c;

  if (argc < 2)
    return 1;

  while (c = argv[1][++i])
    for (j = 2; j < argc; j++)
      if (argv[j][i] != c)
        goto out;

 out:
  printf("Longest common prefix: %.*s\n", i, argv[1]);
}

Skompiluj go, uruchom z listą łańcuchów jako argumentami linii poleceń, a następnie poproś mnie o użycie goto!

Oto rozwiązanie wykorzystujące wyrażenia regularne w Ruby:

def build_regex(string)
  arr = []
  arr << string.dup while string.chop!
  Regexp.new("^(#{arr.join("|")})")
end

def substring(first, *strings)
  strings.inject(first) do |accum, string|
    build_regex(accum).match(string)[0]
  end
end

Wykonałbym następujące czynności:

1. przyjmuje pierwszy łańcuch tablicy jako początkowy podciąg początkowy .
2. weź następny łańcuch tablicy i porównaj znaki, aż do osiągnięcia końca jednego z łańcuchów lub znalezienia niedopasowania. Jeśli wykryto niedopasowanie, zmniejsz podłańcuch początkowy do długości, w której znaleziono niedopasowanie.
3. Powtórz krok 2, aż wszystkie łańcuchy zostaną przetestowane.

Oto JavaScript "realizacja": {]}

var array = ["interspecies", "interstelar", "interstate"],
    prefix = array[0],
    len = prefix.length;
for (i=1; i<array.length; i++) {
    for (j=0, len=Math.min(len,array[j].length); j<len; j++) {
        if (prefix[j] != array[i][j]) {
            len = j;
            prefix = prefix.substr(0, len);
            break;
        }
    }
}

Zamiast sortowania, możesz po prostu uzyskać min i max ciągów.

Dla mnie elegancja w programie komputerowym to równowaga szybkości i prostoty. Nie powinien wykonywać niepotrzebnych obliczeń i powinien być wystarczająco prosty, aby jego poprawność była widoczna.

Rozwiązanie sortowania mógłbym nazwać "sprytnym" , ale nie "eleganckim".

Często bardziej elegancko jest używać dojrzałej biblioteki open source zamiast kręcić własną. Następnie, jeśli nie pasuje do Twoich potrzeb, możesz go rozszerzyć lub zmodyfikować, aby go ulepszyć i pozwolić społeczności zdecydować, czy należy on do biblioteki.

Diff-LCS jest dobrym klejnotem Rubinowym dla najmniej pospolitego podłańcucha.

Moje rozwiązanie w Javie:

public static String compute(Collection<String> strings) {
    if(strings.isEmpty()) return "";
    Set<Character> v = new HashSet<Character>();
    int i = 0;
    try {
        while(true) {
            for(String s : strings) v.add(s.charAt(i));
            if(v.size() > 1) break;
            v.clear();
            i++;
        }
    } catch(StringIndexOutOfBoundsException ex) {}
    return strings.iterator().next().substring(0, i);
}

Golfed js solution just for fun:

w=["hello", "hell", "helen"];
c=w.reduce(function(p,c){
    for(r="",i=0;p[i]==c[i];r+=p[i],i++){}
    return r;
});

Oto skuteczne rozwiązanie w ruby. Oparłem ideę strategii dla zgadywanki hi / lo, w której iteratywnie zerujesz na najdłuższy prefiks.

Ktoś popraw mnie, jeśli się mylę, ale myślę, że złożoność to O (N log n), gdzie n jest długością najkrótszego ciągu, A Liczba łańcuchów jest uważana za stałą.

def common(strings)
  lo = 0
  hi = strings.map(&:length).min - 1
  return '' if hi < lo

  guess, last_guess = lo, hi

  while guess != last_guess
    last_guess = guess
    guess = lo + ((hi - lo) / 2.0).ceil

    if strings.map { |s| s[0..guess] }.uniq.length == 1
      lo = guess
    else
      hi = guess
    end
  end

  strings.map { |s| s[0...guess] }.uniq.length == 1 ? strings.first[0...guess] : ''
end

I kilka sprawdzeń czy działa:

>> common %w{ interspecies interstelar interstate }
=> "inters"

>> common %w{ dog dalmation }
=> "d"

>> common %w{ asdf qwerty }
=> ""

>> common ['', 'asdf']
=> ""

Funny alternative Ruby solution:

def common_prefix(*strings)
  chars  = strings.map(&:chars)
  length = chars.first.zip( *chars[1..-1] ).index{ |a| a.uniq.length>1 }
  strings.first[0,length]
end

p common_prefix( 'foon', 'foost', 'forlorn' ) #=> "fo"
p common_prefix( 'foost', 'foobar', 'foon'  ) #=> "foo"
p common_prefix( 'a','b'  )                   #=> ""

Może to pomóc w szybkości, jeśli użyjesz chars = strings.sort_by(&:length).map(&:chars), ponieważ im krótszy jest pierwszy ciąg, tym krótsze są tablice utworzone przez zip. Jeśli jednak zależy ci na szybkości, prawdopodobnie nie powinieneś używać tego rozwiązania. :)

Javascript clone of AShelly 's excellent answer.

Wymaga Array#reduce, który jest obsługiwany tylko w Firefoksie.

var strings = ["interspecies", "intermediate", "interrogation"]
var sub = strings.reduce(function(l,r) { 
    while(l!=r.slice(0,l.length)) {  
        l = l.slice(0, -1);
    }
    return l;
});

To nie jest bynajmniej eleganckie, ale jeśli chcesz zwięzłe:

Ruby, 71 znaków

def f(a)b=a[0];b[0,(0..b.size).find{|n|a.any?{|i|i[0,n]!=b[0,n]}}-1]end

Jeśli chcesz to rozwiń to wygląda tak:

def f(words)
  first_word = words[0];
  first_word[0, (0..(first_word.size)).find { |num_chars|
    words.any? { |word| word[0, num_chars] != first_word[0, num_chars] }
  } - 1]
end

To nie jest code golf, ale prosiłeś o nieco elegancki, a ja myślę, że rekurencja jest zabawna. Java.

/** Recursively find the common prefix. */
public String findCommonPrefix(String[] strings) {

    int minLength = findMinLength(strings);

    if (isFirstCharacterSame(strings)) {
        return strings[0].charAt(0) + findCommonPrefix(removeFirstCharacter(strings));
    } else {
        return "";
    }
}

/** Get the minimum length of a string in strings[]. */
private int findMinLength(final String[] strings) {
    int length = strings[0].size();
    for (String string : strings) {
        if (string.size() < length) {
            length = string.size();
        }
    }
    return length;
}

/** Compare the first character of all strings. */
private boolean isFirstCharacterSame(String[] strings) {
    char c = string[0].charAt(0);
    for (String string : strings) {
        if (c != string.charAt(0)) return false;
    }

    return true;
}

/** Remove the first character of each string in the array, 
    and return a new array with the results. */
private String[] removeFirstCharacter(String[] source) {
    String[] result = new String[source.length];
    for (int i=0; i<result.length; i++) {
        result[i] = source[i].substring(1); 
    }
    return result;
}

Wersja ruby oparta na algorytmie @ Svante. Działa ~3x tak szybko jak mój pierwszy.

 def common_prefix set 
   i=0
   rest=set[1..-1]
   set[0].each_byte{|c|
     rest.each{|e|return set[0][0...i] if e[i]!=c}
     i+=1
   }
   set
 end

My Javascript rozwiązanie:

IMOP, używanie sortowania jest zbyt trudne. Moim rozwiązaniem jest porównanie litery po literze poprzez zapętlenie tablicy. Return string jeśli litera nie jest macthed.

To jest moje rozwiązanie:

var longestCommonPrefix = function(strs){
    if(strs.length < 1){
        return '';
    }

    var p = 0, i = 0, c = strs[0][0];

    while(p < strs[i].length && strs[i][p] === c){
        i++;
        if(i === strs.length){
            i = 0;
            p++;
            c = strs[0][p];
        }
    }

    return strs[0].substr(0, p);
};

Zdając sobie sprawę z ryzyka, że to zamieni się w meczcode golf (czy taki jest zamiar?), oto moje rozwiązanie za pomocą sed, skopiowane z mojej odpowiedzi na inne pytanie SO i skrócone do 36 znaków (z których 30 to rzeczywiste wyrażenie sed). Oczekuje, że ciągi znaków (każdy w oddzielnej linii) będą dostarczane na standardowym wejściu lub w plikach przekazywanych jako dodatkowe argumenty.

sed 'N;s/^\(.*\).*\n\1.*$/\1\n\1/;D'

Skrypt z sed w linii shebang waży 45 znaków:

#!/bin/sed -f
N;s/^\(.*\).*\n\1.*$/\1\n\1/;D

Test po uruchomieniu skryptu (o nazwie longestprefix), ciągi znaków dostarczane jako "tutaj dokument":

$ ./longestprefix <<EOF
> interspecies
> interstelar
> interstate
> EOF
inters
$