Найти все анаграммы в строке, как оптимизировать

Имея строку s и непустую строку p, найдите все начальные индексы анаграмм p в s.

Пример:-

  • Ввод: с: "cbaebabacd" р: "abc"
  • Выход: [0, 6]
  • Объяснение:
    Подстрока с начальным индексом = 0 называется "cba", что является анаграммой "abc".
    Подстрока с начальным индексом = 6 называется "bac", что является анаграммой "abc".

Я написал этот код на Python для «Найти все анаграммы в строке». Когда я запускаю этот код, он дает мне сообщение Time exceeded:

1) Верна ли моя логика

2) Как я могу оптимизировать, чтобы он мог работать быстрее, так как для больших входных строк требуется много времени (около 1 минуты).

def anagram(s,p):
    if len(p)>len(s):
        return False
    l_s=len(s)
    l_p=len(p)
    list1=[]
    offset=l_p
    k=offset
    i=0
    while (i <= l_s):
        s4=s[i:k]
        #print ("s= "+s4)
        if sorted(p)==sorted(s4):
            list1.append(i)
        i+=1
        k=i+(offset)
    return list1

python anagram
person RAHUL SRIVASTAVA    schedule 14.12.2018    source источник
comment
Что должен делать p? Некоторое объяснение того, что ваши переменные и что вы хотите вывести, было бы хорошо.   -  person ycx    schedule 14.12.2018
comment
Вы запускали профилировщик, чтобы увидеть, где находится горячая точка?   -  person adrtam    schedule 14.12.2018
comment
Я уже упоминал в своем разделе комментариев выше код, касающийся ввода и вывода, например. Найти все анаграммы в строке. Вход: s: cbaebabacd p: abc Выход: [0, 6]. Также моя программа работает с правильным выводом. Только это занимает >1 минуты для большей входной строки длиной >10000. Поэтому мне нужен ввод с точки зрения того, какие изменения я могу внести в свой код, чтобы запустить его быстрее.   -  person RAHUL SRIVASTAVA    schedule 15.12.2018
comment
Пожалуйста, объясните переменные. p и s не очень полезные имена. Кроме того, что означает [0, 6]? Что такое 0? Что такое 6?   -  person bfontaine    schedule 15.12.2018
comment
Когда вы увеличиваете i и k на единицу, вы, по сути, просто добавляете один символ и удаляете один символ в своем s4. Таким образом, вам не нужно снова сортировать, это узкое место. Вместо этого я бы вел словарь.   -  person Autonomous    schedule 15.12.2018
comment
Вот подробности. Имея строку s и непустую строку p, найдите все начальные индексы анаграмм p в s. Дальнейший пример: Ввод: s: cbaebabacd p: abc Вывод: [0, 6] Объяснение: Подстрока с начальным индексом = 0 — это cba, которая является анаграммой abc. Подстрока с начальным индексом = 6 — это bac, которая является анаграммой abc.   -  person RAHUL SRIVASTAVA    schedule 15.12.2018
comment
Ваш цикл while может остановиться на l_s - l_p.   -  person Barmar    schedule 15.12.2018
comment
Вам не нужно вычислять sorted(p) каждый раз в цикле, оно никогда не меняется.   -  person Barmar    schedule 15.12.2018
comment
Даже после сортировки (p) один раз, перемещая его за пределы цикла while, я не вижу улучшения во времени его выполнения. Любая идея, как я могу добавить логику обслуживания словаря и что именно мне нужно сделать после этого, чтобы ускорить.   -  person RAHUL SRIVASTAVA    schedule 15.12.2018

Ответы (1)


arrow_upward
0
arrow_downward

Вам нужно отсортировать p только один раз, так как он никогда не меняется. Вы можете сделать это в начале функции.

Вы должны остановить цикл, когда доберетесь до i = len_s - len_p, так как остальная часть строки короче, чем p.

def anagram(s,p):
    if len(p)>len(s):
        return False
    len_p = len(p)
    sorted_p = sorted(p)
    list1=[]
    for i in range(len(s) - len_p + 1):
        s4=s[i:i+len_p]
        #print ("s= "+s4)
        if sorted_p == sorted(s4):
            list1.append(i)
    return list1
person Barmar    schedule 14.12.2018
comment
Спасибо Бармар за быстрый ответ. Когда я запустил вашу программу, она дала неверные результаты для входных данных (s=abab,p=ab) как [0, 1]. Должно было быть [0, 1, 2]. Моя программа работает нормально, только проблема в том, что она медленная. - person RAHUL SRIVASTAVA; 15.12.2018
comment
Ошибка ограждения, я остановился на 1 символ раньше. - person Barmar; 15.12.2018
comment
Спасибо Бармар. Теперь это работает. Хорошая логика. Но по времени я все еще вижу, что это занимает около минуты. Так что никаких улучшений во времени работы. Это происходит, когда я даю s=1000 (т.е. aaaa........1000 число a) и p=1000 (т.е. aaaa........1000 число a) - person RAHUL SRIVASTAVA; 15.12.2018
comment
s и p - это 1000 символов? Это должно зацикливаться только один раз, поэтому это эквивалентно if sorted(p) == sorted(s): - person Barmar; 15.12.2018
comment
Извините, s было намного больше, чем я сказал. Входные данные следующие: - количество a в s=(aaa......................... .20002 a's) и p=(aaa......................10001 a's). Ответ для этого: [0, 10001] - person RAHUL SRIVASTAVA; 15.12.2018
comment
Этого хватит примерно на 10 000 видов по 10 001 элементу. Это много сортировки, которая будет медленной. - person Barmar; 15.12.2018
comment
Как упоминалось в комментарии, вы можете оптимизировать его, понимая, что вы всегда удаляете 1 символ и добавляете 1 символ. Вы можете вставить новый символ в правильно отсортированное место, вместо того, чтобы повторять сортировку. - person Barmar; 15.12.2018
comment
Я мог бы сделать это за вас, но я думаю, что весь смысл упражнения в том, чтобы вы сами придумали алгоритм. - person Barmar; 15.12.2018
comment
Спасибо Бармар. Я попробую предложение. - person RAHUL SRIVASTAVA; 15.12.2018