2

На вход поступает строка из строчных латинских букв(до 50000 символов), количество подстрок(до 50000), а далее пары чисел, обозначающих первый и последний элемент подстроки.

Пример:

abacaba

3

1 1

1 7

2 4

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

a

a

c

Задание сдается на автоматическое тестирование на сайте. Ограничение по времени 3 сек, по памяти 512 Мбайт. На одном из тестов выдает 3.11/3 сек, тест с максимальными входными данными. Назрел только один вопрос: как можно ускорить алгоритм? По памяти вроде с большим запасом проходит, да и результат верный выдает.

public class TheMostFrequentSymbol {

    public static void main(String[] args) {

        FastScanner in = new FastScanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        String s;
        s = in.next();
        int q;
        q = in.nextInt();
        int[] l = new int[q];
        int[] r = new int[q];
        for (int i = 0; i < q; ++i) {
            l[i] = in.nextInt();
            r[i] = in.nextInt();
        }

        char[] result = new char[q];


        for (int k = 0; k < q; k++) {
            Map<Character, Integer> map = new HashMap<>();
            int max = 0;
            for (int i = l[k] - 1; i < r[k]; i++) {
                char ch = s.charAt(i);
                if (map.containsKey(ch)) {
                    map.put(ch, map.get(ch) + 1);
                } else {
                    map.put(ch, 1);
                }
                if (map.get(ch) >= max) {
                    max = map.get(ch);
                    result[k] = ch;
                }
            }
        }

        for (int i = 0; i < result.length; ++i) {
            out.println(result[i]);
        }

        out.close();
    }

    static class FastScanner {

        BufferedReader br;
        StringTokenizer st;

        FastScanner(InputStream stream) {
            try {
                br = new BufferedReader(new InputStreamReader(stream));
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

  • задание с coursera.org, для самообучения
2
  • Укажите ссылку на сайт с задачей, чтобы было понятно, что она не из какого-нибудь текущего соревнования. А по поводу неизвестного теста, испытайте Ваше решение на максимальном: строка длиной 50000 и 50000 подстрок с 1 по 50000 27 мар 2019 в 12:58
  • 1
    @defaultlocale ссылку указала. А тестирование и правда на максимальных значениях, но вопрос не отпадает. Не вижу каким способ алгоритм ускорить. 27 мар 2019 в 13:05

1 ответ 1

3

Если S — длина строки, а T — количество подстрок, то сложность Вашего алгоритма O(T*S). В худшем случае это примерно 25*10^8 итераций.

Учитывая, что используется ограниченный набор символов, можно построить алгоритм со сложностью O(S+T).

Предрасчет

Для каждой буквы алфавита I (всего 26) и для каждого префикса длины L (первые L символов) заданной строки рассчитаем сколько раз (lettersCount[I][L]) буква встречается в префиксе.

Например, для строки «abacaba»:

  • lettersCount[0][5] = 3, т.к. буква 0 («a») встречается в префиксе длины 5 («abaca») три раза;
  • lettersCount[0][0] = 0;
  • lettersCount[0][1] = 1;
  • lettersCount[2][8] = 1.

Рассчитать lettersCount для всех возможных значений (26 букв X (S+1) возможных длин префиксов) можно одним проходом по строке.

Подстроки

Используем предрасчитанные значения чтобы расчитать ответ для каждой заданной подстроки (с X по Y) не пробегаясь по ней.

С помощью формулы lettersCount[I][Y] - lettersCount[I][X-1] можно определить сколько раз в подстроке встречается буква с индексом I.

Например: буква «a» встречается в подстроке с 2 по 5: lettersCount[0][5] - lettersCount[0][1] = 3 - 1 = 2 раза.

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

Всего потребуется примерно 26*S + 26*Т итераций, что должно уложиться в лимит времени.

1
  • 1
    элегантное решение, плюс от меня :)
    – tym32167
    27 мар 2019 в 14:16

Ваш ответ

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

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