Найдите самую длинную общую стартовую подстроку в ряде строк [закрытой]

Рубиновая версия, основанная на алгоритме @Svante. Работает примерно в 3 раза быстрее, чем мой первый.

 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

Это не кодовый гольф, но вы просили немного элегантности, и я склонен думать, что рекурсия - это весело. 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;
}

Клон Javascript отличного ответа AShelly .

Требуется Array # reduce , который поддерживается только в firefox.

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

Это ни в коем случае не изящно, но если вы хотите краткости:

Ruby, 71 символ

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

Если вы хотите, чтобы это развернулось, это выглядит так:

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

Вот решение, использующее регулярные выражения в 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

Однострочник Ruby:

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

Мой однострочный текст Haskell:

import Data.List

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

РЕДАКТИРОВАТЬ: barkmadley дал хорошее объяснение приведенного ниже кода. Я бы также добавил, что haskell использует ленивое вычисление, поэтому мы можем лениться в отношении использования транспонирования ; он будет перемещать наши списки только настолько, насколько это необходимо, чтобы найти конец общего префикса.

Вам просто нужно пройти по всем строкам, пока они не станут отличаться, а затем взять подстроку до этого момента.

Псевдокод:

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

Это, вероятно, не самое краткое решение (зависит от того, есть ли у вас уже библиотека для этого), но один из элегантных методов - использовать дерево. Я использую попытки для реализации завершения табуляции в моем интерпретаторе схемы:

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

Например:

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

Я также использую их для сопоставление имен каналов с символами подстановки для протокола Байё; см. эти:

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

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

Это не кажется таким уж сложным, если вы не слишком озабочены конечной производительностью:

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

Одной из полезных функций инъекции является возможность предварительного заполнения с первым элементом массив, над которым выполняется взаимодействие. Это позволяет избежать проверки на ноль.

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"

Обновление: Если здесь игра в гольф, то 67 символов:

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

В Python я бы не использовал ничего, кроме существующую функцию commonprefix я показал в другом ответе, но я не мог не изобрести колесо : P . Это мой подход на основе итератора:

>>> 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: Объяснение того, как это работает.

zip генерирует кортежи элементов, принимая по одному из каждого элемента a за раз:

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

Сопоставляя набор этим элементам, я получаю серию уникальных букв:

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) берет элементы из этого, пока предикат истинен; в данном конкретном случае, когда набор имеет один элемент, то есть все слова имеют одну и ту же букву в этой позиции:

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

В этот момент у нас есть итерация наборов, каждое из которых содержит одну букву префикс, который мы искали. Чтобы построить строку, мы объединяем их в одну итерацию, из которой получаем буквы для соединения в конечной строке.

Магия использования итераторов заключается в том, что все элементы генерируются по запросу, поэтому, когда takewhile перестает запрашивать элементы, сжатие останавливается на этом этапе и ненужная работа не выполняется. Каждый вызов функции в моем однострочном носителе имеет неявный для и неявный разрыв .

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

На этом этапе у нас есть итерация множеств, каждое из которых содержит одну букву искомого префикса. Чтобы построить строку, мы объединяем их в одну итерацию, из которой получаем буквы для соединения в конечной строке.

Магия использования итераторов заключается в том, что все элементы генерируются по запросу, поэтому, когда takewhile перестает запрашивать элементы, сжатие останавливается на этом этапе и ненужная работа не выполняется. Каждый вызов функции в моем однострочном носителе имеет неявный для и неявный разрыв .

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

На этом этапе у нас есть итерация множеств, каждое из которых содержит одну букву искомого префикса. Чтобы построить строку, мы объединяем их в одну итерацию, из которой получаем буквы для соединения в конечной строке.

Магия использования итераторов заключается в том, что все элементы генерируются по запросу, поэтому, когда takewhile перестает запрашивать элементы, сжатие останавливается на этом этапе и ненужная работа не выполняется. Каждый вызов функции в моем однострочном носителе имеет неявный для и неявный разрыв .

Магия использования итераторов заключается в том, что все элементы создаются по запросу, поэтому, когда takewhile перестает запрашивать элементы, сжатие прекращается на этом этапе и ненужная работа не выполняется. Каждый вызов функции в моем однострочном носителе имеет неявный для и неявный разрыв .

Магия использования итераторов заключается в том, что все элементы создаются по запросу, поэтому, когда takewhile перестает запрашивать элементы, сжатие прекращается на этом этапе и ненужная работа не выполняется. Каждый вызов функции в моем однострочном носителе имеет неявный для и неявный разрыв .

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 для i в диапазоне (min (map (len, a))) , максимальное количество поисков не может быть больше длины самой короткой строки; в этом примере это будет вычисляться как [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

• len (set (map (lambda e: e [i], a) )) , 1) создать массив i-го символа для каждой строки в списке; 2) сделать из него набор; 3) определить размер набора

• [i for i in range (min (map (len, a))) if len (set (map (lambda e: e [i], a))) == 1] , включайте только символы, для которых размер набора равен 1 (все символы в этой позиции были одинаковыми ..); здесь он будет оцениваться как [0, 1, 2, 3, 4, 5]

• , наконец, взять max , добавить единицу и получить подстроку ...

Примечание: указанное выше не работает для a = ['intersyate', 'intersxate', 'interstate', 'intertersrate'] , но это будет:

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

Это очень похоже на решение Роберто Бонвалле, за исключением рубина.

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

В первой строке каждое слово заменяется массивом символов. Затем я использую zip для создания этой структуры данных:

[[«i», «i», «i»], [«n», «n», «n»], [«t», «t», «t»],. ..

map и uniq сокращают это до [["i"], ["n"], ["t"], ...

take_ while извлекает символы из массива, пока не найдет тот, размер которого не равен единице (то есть не все символы были одинаковыми). Наконец, я соединяю их снова вместе.

Просто для удовольствия, вот версия, написанная в (SWI-) PROLOG:

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

Запуск:

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

Дает:

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

Пояснение:

(SWI-) PROLOG рассматривает строки как списки кодов символов (чисел). Все, что делает предикат common_pre / 2 , - это рекурсивное сопоставление с образцом для выбора первого кода ( C ) из заголовка первого списка (строка, [C | Cs] ) в списке всех списков (все строки, [[C | Cs] | Ss] ) и добавляет соответствующий код C к результату iff он является общим для всех (оставшихся) заголовков всех списков (строк), иначе он завершается.

Красиво, чисто, просто и эффективно ... :)

Еще один способ сделать это: использовать 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

И однострочник, любезно предоставлен mislav (50 символов):

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

Я бы сделал следующее:

1. Возьмем первую строку массива как начальную начальную подстроку .
2. Возьмем следующую строку массива и сравните символы до тех пор, пока не будет достигнут конец одной из строк или не будет обнаружено несоответствие. Если обнаружено несоответствие, сократите начальную подстроку до длины, на которой было обнаружено несоответствие.
3. Повторяйте шаг 2, пока не будут проверены все строки.

Вот реализация JavaScript:

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

В Python:

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