Greetings.

Given K arrays (0 <K <10) containing strings. It is necessary to find the largest (by the number of characters) string found in all K arrays. Do not advise the algorithm or code?

Thank you in advance.

  • It would be clear, I would not write here. - andrewshka

3 answers 3

Solution for line

  1. We get a hash map from a string into a bit mask of size K
  2. For each line, we replace the bit mask associated with it with the same one, but with the one in the bit corresponding to the array number.
  3. In one pass, we find in the hash map a string of maximum length with a bitmask of the form 11111111 .

Pseudo java code:

 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);
  • Cool, and can any example with the code? Language is not important. Thank! - andrewshka
  • @Jofsey: why so difficult? Why not display a string on the number of arrays? - VladD
  • 2
    @VladD is also possible, but then either before increasing the counter, you will have to check if the same line did not occur in the same array before, or for each line to check its presence in each of the arrays, which is no longer in line. - Jofsey
  • 2
    @Vlad, the same string can appear in the same array several times. - dzhioev
  • @VladD I will write pseudocode. If you know how to succinctly get rid of bitmasks while preserving the asymptotics - write. - Jofsey

@andrewshka taking into account the unimportance of the language, here is an example

 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 yx) $ map (\x -> (x, length x)) $ S.toList $ foldl1' S.intersection $ map S.fromList input main = print out
  • Hmm, what if the intersection is empty, will it work? - VladD
  • @VladD *** Exception: Prelude.head: empty list Then case l of {[] -> print "figa"; h: _ -> print h} - alexlz
  • @alexlz: but there is no built-in analogue of FirstOrDefault with option ? - VladD
  • one
    @VladD for head? Did not see firstOrDefault l default = case l of {[] -> default; h: _ -> h} So? Now there is :) - alexlz
  • one
    @VladD out = (\ s -> if S.null s then "No such" else fst $ head $ sortBy (( , x) ( , y) -> compare yx) $ map (\ x -> (x, length x)) $ S.toList s) $ foldl1 'S.intersection $ map S.fromList input main = putStrLn out And if Maybe monads are very popular, then 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 yx) >> = Just. fst. head main = putStrLn $ case out of {Nothing -> "No such"; Just x -> x} - alexlz

If the language is not important, here’s C #:

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

Or so:

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

(the search speed of the intersection O (total size), the speed of the combination OrderBy + First O (the size of the intersection)).