0

Приветствую.

Дано K массивов (0 < K < 10) содержащих строки. Необходимо найти наибольшую (по количеству символов) строку, находящуюся во всех K массивах. Не посоветуете алгоритм или код?

Заранее спасибо.

1
  • Было бы понятно, я бы сюда не писал.
    – andrewshka
    24 мая 2013 в 17:52

3 ответа 3

2

Решение за линию

  1. Заводим хеш-мап из строки в битовую маску размера K.
  2. Для каждой строки заменяем ассоциированную с ней битовую маску на такую же, но с единичкой в разряде, соответсвующем номеру массива.
  3. За один проход находим в хеш-мапе строку максимальной длины с битовой маской вида 11111111.

Псевдо-джава-код:

String[][] arrays = ...; //ввод данных
Map<String, Integer> map = new HashMap<>();
for (int k = 0; k < arrays.length; k++) {
    for (String str: arrays[k]) {
        int mask = 1 << k;
        if (map.contains(str)) {
            map.put(str, map.get(str) & mask);
        } else {
            map.put(str, mask);
        }
    }
}

String longest = "";
for (String str : map.getKeys()) {
    if (map.get(str) == (1 << input.length) - 1
            && longest.lenght < str.length) {
        longest = str;
    }
}
System.out.println(longest);
9
  • Круто, а можно какой-нибудь пример с кодом? Язык не важен. Спасибо!
    – andrewshka
    24 мая 2013 в 17:53
  • @Jofsey: а зачем так сложно? Почему не отображать строку на количество массивов?
    – VladD
    24 мая 2013 в 18:15
  • 2
    @VladD тоже можно, но тогда либо перед увеличением счётчика придётся проверять не встречалась ли эта же строка в этом же массиве ранее, либо для каждой строки проверять её присутствие в каждом из массивов, что уже не за линию. 24 мая 2013 в 18:39
  • 2
    @Vlad, одна и та же строка может встречаться в одном массиве несколько раз.
    – dzhioev
    24 мая 2013 в 18:39
  • @VladD щас напишу псевдокод. Если знаете как лаконично избавиться от битовых масок с сохранением асимптотики -- пишите. 24 мая 2013 в 18:40
0

@andrewshka с учётом неважности языка, вот пример

import Data.List (sortBy, foldl1')
import qualified Data.Set as S
input = [["abracadabra", "good", "fuck"], ["abracadabra", "bad", "fuck"], ["abracadabra", "aaaaaaaaaaaaaaaaaaaaaa", "fuck", "fuck"]]
out = fst $ head $ sortBy (\(_,x) (_,y) -> compare y x) $ map (\x -> (x, length x)) $ S.toList $ foldl1' S.intersection $ map S.fromList input
main = print out
10
  • Хм, а если пересечение пусто, сработает?
    – VladD
    24 мая 2013 в 19:11
  • @VladD *** Exception: Prelude.head: empty list Тогда case l of {[] -> print "figa"; h:_ -> print h}
    – alexlz
    24 мая 2013 в 19:25
  • @alexlz: а нету встроенного аналога FirstOrDefault с option?
    – VladD
    24 мая 2013 в 19:38
  • 1
    @VladD для head? Не видел firstOrDefault l default = case l of {[] -> default; h:_ -> h} Так? Теперь есть :)
    – alexlz
    24 мая 2013 в 19:44
  • 1
    @VladD out = (\s -> if S.null s then "Нет таких" else fst $ head $ sortBy ((,x) (,y) -> compare y x) $ map (\x -> (x, length x)) $ S.toList s) $ foldl1' S.intersection $ map S.fromList input main = putStrLn out А если сильно нравятся монады Maybe, то out = Just input >>= Just . map S.fromList >>= Just . foldl1' S.intersection >>= (\x -> if S.null x then Nothing else Just x) >>= Just . S.toList >>= Just . map (\x -> (x, length x)) >>= Just . sortBy ((,x) (,y) -> compare y x) >>= Just . fst . head main = putStrLn $ case out of {Nothing -> "Нет таких"; Just x -> x}
    – alexlz
    25 мая 2013 в 3:03
0

Если язык не важен, вот вам C#:

arrays.First()
      .Where(s => arrays.Skip(1).All(a => a.Contains(s))
      .OrderByDescending(s => s.Length)
      .FirstOrDefault()

Или так:

arrays.Aggregate((intersection, next) => intersection.Intersect(next))
      .OrderByDescending(s => s.Length)
      .FirstOrDefault();

(скорость поиска пересечения O(суммарного размера), скорость комбинации OrderBy + First О(размера пересечения)).

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.