Поиск индекса перестановки в строке

Question

Я только что попытался выполнить задачу программирования, которую я не смог успешно завершить. Спецификация должна читать 2 строки ввода от System.in.

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

Например, мы можем иметь:

dog cat rat 
abcratdogcattgh 
3 

Где 3 результат (как напечатано System.out).

Это легально иметь дублированный слово в списке:

dog cat rat cat 
abccatratdogzzzzdogcatratcat 
16 

Код, который я продюсировал работал при условии, что слова о том, что ответ начинается с не произошло ранее. Во 2-ом примере здесь, мой код будет не потому, что dog уже появился перед где ответ начинается с индексом 16.

Моя теория была:

1. Найти индекс, где каждое слово встречается в строке
2. Extract этой подстроки (как у нас есть ряд известных слов с известной длиной, это возможно)
3. Убедитесь, что все слова встречаются в подстроках
4. Если они, возвращают индекс, который происходит эта подстрока в исходной строке

Вот мой код (он должен быть скомпилирован):

import java.io.BufferedReader; 
import java.io.InputStreamReader; 

public class Solution { 
    public static void main(String[] args) throws Exception { 
     BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 

     String line = br.readLine(); 
     String[] l = line.split(" "); 
     String s = br.readLine(); 

     int wl = l[0].length(); 
     int len = wl * l.length; 
     int sl = s.length(); 

     for (String word : l) { 
      int i = s.indexOf(word); 
      int z = i; 
      //while (i != -1) { 
       int y = i + len; 
       if (y <= sl) { 
        String sub = s.substring(i, y); 
        if (containsAllWords(l, sub)) { 
         System.out.println(s.indexOf(sub)); 
         System.exit(0); 
        } 
       } 
       //z+= wl; 
       //i = s.indexOf(word, z); 
      //} 
     } 
     System.out.println("-1"); 
    } 

    private static boolean containsAllWords(String[] l, String s) { 
     String s2 = s; 

     for (String word : l) { 
      s2 = s2.replaceFirst(word, ""); 
     } 

     if (s2.equals("")) 
      return true; 
     return false; 
    } 
} 

Я могу решить мою проблему и сделать его пройти 2-й примера, убрав комментирование петли while. Однако это имеет серьезные последствия для производительности. Когда у нас есть ввод из 100 слов по 10 символов каждый и строка из 1000000 символов, время, затраченное на завершение, просто ужасно.

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

Что было бы лучшим способом подойти и решить эту проблему? Я чувствую себя побежденным.

Answer 1

Если вы объединяете строки и используете новую строку для поиска.

String a = "dog" 
String b = "cat" 
String c = a+b; //output of c would be "dogcat" 

Нравится программа? Поделись с друзьями!

Но это не сработает, если catdog также является допустимым значением.

Answer 2

Вот подход (псевдокод)

stringArray keys(n) = {"cat", "dog", "rat", "roo", ...}; 
string bigString(1000000); 
L = strlen(keys[0]); // since all are same length 
int indices(n, 1000000/L); // much too big - but safe if only one word repeated over and over 

for each s in keys 
    f = -1 
    do: 
    f = find s in bigString starting at f+1 // use bigString.indexOf(s, f+1) 
    write index of f to indices 
    until no more found 

Когда вы все сделали, вы будете иметь ряд показателей (место первой буквы матча). Теперь наступает сложная часть. Поскольку слова имеют одинаковую длину, мы ищем последовательность индексов, все они расположены одинаково в 10 разных «коллекциях». Это немного утомительно, но оно должно завершиться за конечное время. Обратите внимание, что это делается быстрее, чем для сравнения строк (сравнение чисел выполняется быстрее, чем проверка соответствия полной строки, очевидно). Я бы снова разбил его на две части - сначала найду «любую последовательность из 10 совпадений», затем «посмотрим, является ли это уникальной перестановкой».

sIndx = sort(indices(:)) 
dsIndx = diff(sIndx); 
sequence = find {n} * 10 in dsIndx 
for each s in sequence 
    check if unique permutation 

Надеюсь, вам это удастся.

Answer 3

Возможно, не самый лучший оптимизированный вариант, но как о следовании теории, чтобы дать вам некоторые идеи:

1. длина Граф всех слов в строке.
2. Возьмите случайное слово из списка и найдите начальный индекс его первого .
3. Возьмите подстроку с длиной, подсчитанной выше до и после этого указатель (например, если индекс имеет 15 и 3 слова длиной 4 буквы, возьмите подстроку с 15-8 до 15 + 11).
4. Сделайте копию списка слов с ранее удаленным случайным словом.
5. Проверьте, добавляются ли/добавляются буквы [word_length], чтобы увидеть, соответствуют ли они новое слово в списке.
6. Если слово соответствует копии списка, удалите его из копии списка и перейдите далее
7. Если все слова, найденные, перерыв петля.
8. Если найдены не все слова, найти начальный индекс следующего совпадения ранее случайное слово и вернуться к 3.

Почему это помогло бы:

• Какое слово вы выбираете, чтобы начать с не имеет значения, так как каждое слово должно быть в полном совпадении.
• Вам не нужно вручную прокручивать множество символов, , если не существует много близких полных ложных совпадений.
• Поскольку предполагаемый матч продолжает расти, у вас меньше слов в списке, оставшихся для сравнения.
• Можно также отслеживать или дальнюю индекс вы пошли на, так что вы можете иногда ограничивать обратную длину подстроки выбрали (как не может перекрываться, где вы уже были, если вхождение в дороге недалеко друг Другие).