Найти самую длинную общую начальную подстроку в наборе строк

Ответ 1

Это вопрос вкуса, но это простая версия javascript: Он сортирует массив, а затем смотрит только на первый и последний элементы.

//самая длинная обычная стартовая подстрока в массиве

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

ДЕМОНСТРАЦИИ

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

Ответ 2

В Python:

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

Ответ 3

Ruby one-liner:

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

Ответ 4

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

псевдокод:

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

Общий 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))))

Ответ 5

Мой Haskell с одним слоем:

import Data.List

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

EDIT: barkmadley дал хорошее объяснение приведенному ниже кодексу. Я бы также добавил, что haskell использует ленивую оценку, поэтому мы можем лениться о нашем использовании transpose; он будет только переносить наши списки, насколько это необходимо, чтобы найти конец общего префикса.

Ответ 6

Еще один способ сделать это: использовать жадность regex.

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]

Ответ 7

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

Изменить: Объяснение того, как это работает.

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

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

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

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

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

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

Ответ 8

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

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"

Я также использую их для сопоставления имен каналов с подстановочными знаками для протокола Bayeux; см. следующие:

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

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

Ответ 9

Просто для удовольствия, здесь версия, написанная в (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 к результату, если он является общим для всех (оставшихся) глав всех списков (строк), иначе он завершается.

Хороший, чистый, простой и эффективный...:)

Ответ 10

Версия javascript на основе алгоритма @Svante:

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

Ответ 11

Объединив ответы kennebec, Florian F и jberryman, вы получите следующий однострочный Haskell:

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

С Control.Arrow можно получить беспутную форму:

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

Ответ 12

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

• len(set(map(lambda e: e[i], a))), 1) создать массив символа i-th для каждой строки в списке; 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', 'intersrate'], но это:

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

Ответ 13

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

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

Ответ 14

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

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 вытягивает символы из массива, пока не найдет тот, где размер не один (что означает не все символы одинаковы). Наконец, я join их обратно вместе.

Ответ 15

принятое решение нарушено (например, он возвращает a для строк типа ['a', 'ba']). Исправление очень просто, вы буквально должны изменить только 3 символа (от indexOf(tem1) == -1 до indexOf(tem1) != 0), и функция будет работать как ожидалось.

К сожалению, когда я попытался отредактировать ответ, чтобы исправить опечатку, SO сказал мне, что "редактирование должно быть не менее 6 символов". Я мог бы изменить больше этих трех символов, улучшив именование и читаемость, но это немного похоже на.

Итак, ниже приведена фиксированная и улучшенная (по крайней мере, с моей точки зрения) версия решения 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;
}

(на jsFiddle)

Обратите внимание, что он использует метод reduce (JavaScript 1.8), чтобы найти буквенно-числовое значение max/min вместо сортировки массива и затем извлечение первого и последнего его элементов.

Ответ 16

При чтении этих ответов со всем фантастическим функциональным программированием, сортировкой и регулярными выражениями и еще много чего, я просто подумал: что плохого в C? Итак, вот тупо выглядящая маленькая программа.

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

Скомпилируйте его, запустите его со списком строк в качестве аргументов командной строки, а затем отпустите меня для использования goto!

Ответ 17

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

Ответ 18

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

• Возьмите первую строку массива как начальную начальную подстроку.
• Возьмите следующую строку массива и сравните символы до тех пор, пока не будет достигнут конец одной из строк или не будет обнаружено несоответствие. Если обнаружено несоответствие, уменьшите начальную подстроку до длины, где обнаружено несоответствие.
• Повторите шаг 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;
        }
    }
}

Ответ 19

Вместо сортировки вы можете просто получить min и max строк.

Для меня элегантность в компьютерной программе - это баланс скорости и простоты. Он не должен делать ненужных вычислений, и он должен быть достаточно простым, чтобы сделать его правильность очевидной.

Я мог бы назвать сортировочное решение "умным", но не "элегантным".

Ответ 20

Зачастую более элегантно использовать зрелую библиотеку с открытым исходным кодом, а не сворачивать самостоятельно. Затем, если это не полностью соответствует вашим потребностям, вы можете расширить его или изменить его, чтобы улучшить его, и позволить сообществу решить, принадлежит ли это в библиотеке.

diff-lcs - хороший камень Ruby для наименьшей общей подстроки.

Ответ 21

Мое решение в Java:

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

Ответ 22

Golfed JS решение просто для удовольствия:

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

Ответ 23

Здесь эффективное решение в рубине. Я основывал идею стратегии игры hi/lo угадывания, где вы итерационно нулевым на самом длинном префиксе.

Кто-то исправит меня, если я ошибаюсь, но я считаю, что сложность - это O (n log n), где n - длина кратчайшей строки, а число строк считается константой.

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

И некоторые проверки, в которых он работает:

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

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

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

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

Ответ 24

Интересное альтернативное решение Ruby:

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'  )                   #=> ""

Это может ускорить работу, если вы использовали chars = strings.sort_by(&:length).map(&:chars), поскольку чем короче первая строка, тем короче массивы, созданные zip. Однако, если вы заботитесь о скорости, вы, вероятно, не должны использовать это решение.:)

Ответ 25

Это отнюдь не изящно, но если вы хотите лаконично:

Ruby, 71 chars

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

Ответ 26

Клон Javascript Как бы то ни было отличный ответ.

Требуется 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;
});

Ответ 27

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

Ответ 28

Рубиновая версия, основанная на алгоритме @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

Ответ 29

Мое решение Javascript:

IMOP, использование сортировки слишком сложно. Мое решение сравнивает букву с буквой, зацикливая массив. Возвращаемая строка, если буква не указана.

Это мое решение:

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

Ответ 30

Понимая риск превращения этого поворота в матч code golf (или это намерение?), здесь мое решение с использованием sed, скопированное из мой ответ на другой вопрос SO и сокращен до 36 символов (30 из которых являются фактическим выражением sed). Он ожидает, что строки (каждая на отдельной строке) будут поставляться на стандартном входе или в файлах, переданных в качестве дополнительных аргументов.

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

A script с sed в линии shebang весит 45 символов:

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

Тестирование script (с именем longestprefix) с строками, представленными как "здесь документ":

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