Каттис "за субтитры" нестандартной расшифровки вызов


Я написал функцию, чтобы решить проблему в Java, но это все-таки тоже перебор, и я бы хотел, чтобы оптимизировать с точки зрения времени выполнения.

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

Что я пробовал ниже код, чтобы перейти на зашифрованный символ строки на символ (для длины моего ключа каждый раз), и попытаться сделать словарь. Если бы я мог успешно назначить каждого символа из ключа, чтобы персонаж из зашифрованного текста детерминированным образом, то я записываю это в счетчик, и начать со следующего символа в зашифрованном тексте.

До сих пор это решение работает на все испытания, пока не достигнет огромного тестовый случай, где мое решение "грубой силы" превысил лимит времени.

Любой идеи, как я могу улучшить производительность или попробовать другой подход?

package chasingsubs;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;

public class ChasingSubs {

    private void decrypt(String line, String key) {
        int counter = 0;
        int startIndex = 0;
        for (int i = 0; i < line.length() - key.length() + 1; i++) {
            HashMap<Character, Character> dictionary = new HashMap<>();
            HashSet<Character> used = new HashSet<>();

            for (int j = 0; j < key.length(); j++) {
                Character keyChar = key.charAt(j);
                Character sourceChar = line.charAt(i+j);

                if (dictionary.get(keyChar) == null) {
                    if (!used.contains(sourceChar)) {
                        dictionary.put(keyChar, sourceChar);
                        used.add(sourceChar);
                    }else{
                        break;
                    }
                } else if (!dictionary.get(keyChar).equals(sourceChar)) {
                    break;
                }

                if (j == key.length() - 1) {
                    counter++;
                    if (counter == 1) {
                        startIndex = i;
                    }         
                }
            }
        }
        if (counter == 0) {
            System.out.println("0");
            return;
        }
        if (counter == 1) {
            System.out.println(line.substring(startIndex, startIndex + key.length()));
            return;
        }
        System.out.println(counter);
    }

    public static void main(String[] args) {
        ChasingSubs base = new ChasingSubs();
        Scanner scanner = new Scanner(System.in);
        base.decrypt(scanner.nextLine(), scanner.nextLine());
    }

}


Комментарии
1 ответ

Альтернативный подход

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

public static int buildNextArray(String s) {
int[] next = new int[s.length() - 1];
for (int i = 0; i < next.length; i++) {
next[i] = s.indexOf(s.charAt(i), i + 1) - i;
}

return next;
}

Это преобразует строку в уникальный массив, содержащий соответствующую информацию: как далеко находится следующий экземпляр этого символа в строке? Теперь, если вы строите для расшифрованного ключа совпадает с частью массива по зашифрованной линии, то это можно шифра матч.

Я оставлю именно для вас, чтобы развиваться. Обратите внимание, что отрицательное число в массиве ключа может соответствовать неравные числа в массив для строки. Вы можете хотеть думать о том, когда он может соответствовать и когда он не может соответствовать.

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


абвгдежзийклмнопрстуфхцчшщыэюя
abca

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

Это также экономит затраты на HashSet и HashMap обращается. Вместо этого, вы можете делать такие доступы.

Некоторые другие замечания кодирования, который не влияет на производительность:

Код к интерфейсу


            HashMap<Character, Character> dictionary = new HashMap<>();
HashSet<Character> used = new HashSet<>();

Это может быть

            Map<Character, Character> dictionary = new HashMap<>();
Set<Character> used = new HashSet<>();

Это не имеет большого значения, но в целом, вы хотите код на интерфейс. Это делает его легче для переключения реализаций позже.

Делегат


        for (int i = 0; i < line.length() - key.length() + 1; i++) {
HashMap<Character, Character> dictionary = new HashMap<>();
HashSet<Character> used = new HashSet<>();

for (int j = 0; j < key.length(); j++) {
Character keyChar = key.charAt(j);
Character sourceChar = line.charAt(i+j);

if (dictionary.get(keyChar) == null) {
if (!used.contains(sourceChar)) {
dictionary.put(keyChar, sourceChar);
used.add(sourceChar);
}else{
break;
}
} else if (!dictionary.get(keyChar).equals(sourceChar)) {
break;
}

if (j == key.length() - 1) {
counter++;
if (counter == 1) {
startIndex = i;
}
}
}
}


Это становится намного проще, если вы сделаете вспомогательный метод.

    public bool canMatch(String haystack, String needle) {
Map<Character, Character> dictionary = new HashMap<>();
Set<Character> used = new HashSet<>();

for (int j = 0; j < needle.length(); j++) {
Character keyChar = needle.charAt(j);
Character sourceChar = haystack.charAt(j);

if (dictionary.get(keyChar) == null) {
if (used.contains(sourceChar)) {
return false;
}

dictionary.put(keyChar, sourceChar);
used.add(sourceChar);
} else if (!dictionary.get(keyChar).equals(sourceChar)) {
return false;
}
}

return true;
}

Я перевернулся вокруг какой-то внутренней логики. Я нахожу if (false)/else структура запутанным. Я бы предпочел увидеть правду. И в этом случае, это также означает, что мы можем избавиться от elseв качестве оригинальных else статья завершается возвращение (перерыв). Это имеет побочный эффект-уменьшение отступа на другой пункт, который иногда может быть полезным.

Теперь, если игла матчей, мы можем вернуть true. В противном случае, мы возвращаем значение false. Это позволяет нам изменять абонента

    for (int i = 0; counter == 0 && i < 1 + line.length() - key.length(); i++) {
if (canMatch(line.substring(i), key)) {
counter++;
startIndex = i;
}
}

if (counter == 0) {
return "0";
}

for (int i = startIndex + 1; i < 1 + line.length() - key.length(); i++) {
if (canMatch(line.substring(i), key)) {
counter++;
}
}

if (counter == 1) {
return line.substring(startIndex, startIndex + key.length());
}

return Integer.toString(counter);

Теперь нам не придется сравнивать j до последнего индекса ключа на каждой итерации. Вспомогательный метод будет возвращать только true, если это было правдой.

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

1
ответ дан 16 февраля 2018 в 10:02 Источник Поделиться