Има колекция от низове за въвеждане и колекция от низове за заявки. За всеки низ на заявка определете колко пъти се среща в списъка с входни низове.

Например дадени входни низове = ['ab', 'ab', 'abc']и заявки = ['ab', 'abc', 'bc'] , намираме 2съществувания на 'ab', 1 на „abc“ и от 0 от „bc“. За всяка заявка добавяме елемент към нашия върнат масив, резултати = [2, 1, 0].

Въведен формат

Първият ред съдържа цяло число n, размерът на низовете.
Всеки от следващите nредове съдържа низ низове[i].
Следващият ред съдържа q, размера на заявките.
Всеки от следващите qредове съдържа низ q[i].

Ограничения

1<= n <= 1000
1 <= 1 <= 1000
1 <= |strings[i]|, |queries[i]| <=20

Изходен формат

Връща масив от цели числа от резултатите на всички заявки по ред.

Вход

4 aba baba aba xzxb 
3 aba xzxb ab

Изход

2
1
0

Решение

Оптималното решение за това би било да се приложи суфиксно дърво и да се изпълни алгоритъм за съпоставяне на низ O(n).

Направих това обаче само за да демонстрирам помощни функции в Java. По-късно ще демонстрирам решението с помощта на суфиксно дърво.

Най-наивното решение беше просто да се създаде хеш карта на низоветеs. Ключът е дължината, а стойностите са самият низ. По този начин, когато разглеждаме заявките, ще разглеждаме само низове с еднаква дължина. Това ни позволи да оптимизираме (малко) неоптималното решение :)

След като имаме тази карта, ние просто итерираме масива от заявки, извличаме всички низове, чиято дължина е същата като текущия q[j] и оттам използваме API за колекции, за да проверим честотата на конкретен низ в върнатия списък. Collections.frequency()е основно итеративно и изчерпателно търсене на целия ArrayList за срещания на конкретния низ. Това довежда това неоптимално решение до O(n²).

static int[] matchingStrings(String[] strings, String[] queries) {
        Map<Integer, List<String>> map = new HashMap<>();

        for(int i=0; i<strings.length; i++){
            List<String> str = map.get(strings[i].length());
            if (str == null){
                str = new ArrayList<>();
            }
            str.add(strings[i]);

            map.put(strings[i].length(), str);
        }

        int[] count = new int[queries.length];

        for(int j=0; j<queries.length; j++){
            List<String> s = map.get(queries[j].length());
            count[j] = s != null ? 
                       Collections.frequency(s, queries[j]) : 0;
        }

        return count;
    }