Как найти все уникальные подстроки очень длинной строки?

У меня очень длинная строка. Я хочу найти все уникальные подстроки этой строки. Я попытался написать код, в котором я использовал набор (python) для хранения всех подстрок, чтобы обеспечить уникальность. Я получаю правильный результат для многих средних и больших строк, однако в случае очень больших строк я получаю MemoryError. Я немного поработал в Google и обнаружил, что структура данных набора в python имеет большой объем памяти и, возможно, именно поэтому я получаю MemoryError.

Вот мой код:

a = set() for i in range(n): string = raw_input() j = 1 while True: for i in xrange(len(string)-j+1): a.add(string[i:i+j]) if j==len(string): break j+=1 print sorted(list(a)) 

Есть ли способ избежать этой ошибки для больших строк? Или кто-нибудь может предложить лучшую модификацию моего кода для решения этой проблемы?

PS: У меня нет возможности переключаться между 32-битными и 64-битными версиями.

  • Python Реализация шаблона проектирования пула объектов
  • Какова наиболее эффективная структура данных графа в Python?
  • Какова цель коллекций. ChainMap?
  • Почему мой питон python становится неупорядоченным?
  • Смешивание категориальных и непрерывных данных в классификаторе Naive Bayes с использованием scikit-learn
  • Использование памяти DBSCAN scikit-learn
  • 2 Solutions collect form web for “Как найти все уникальные подстроки очень длинной строки?”

    Если вам это действительно нужно в памяти, вы можете попробовать создать дерево суффикса. Ошибки не являются экзотическими структурами данных, поэтому, возможно, существуют хорошие реализации для основного языка, такого как Python, и они могут использоваться для реализации суффиксов. Предполагается, что Marisa-Trie получит хорошее использование памяти.

    1. Создайте пустое три.
    2. Для каждого n из [0, len (s)] добавьте суффикс длины n в Trie.
    3. Каждый путь из корня trie является подстрокой в ​​строке, нет таких путей, которые не являются подстроками в строке, а пути уникальны.

    Вот несколько кода Python, основанных на конструкции дерева суффикса O (n), чтобы создать уникальные подстроки из коллекции входных строк (вывод должен отображаться в отсортированном порядке, поэтому нет необходимости сортировать строки после этого).

    Так как выводные строки O (n ^ 2) могут потребовать много времени для вывода всех строк.

     from collections import defaultdict class SuffixTree: def __init__(self): """Returns an empty suffix tree""" self.T='' self.E={} self.nodes=[-1] def add(self,s): """Adds the input string to the suffix tree. This inserts all substrings into the tree. End the string with a unique character if you want a leaf-node for every suffix. Produces an edge graph keyed by (node,character) that gives (first,last,end) This means that the edge has characters from T[first:last+1] and goes to node end.""" origin,first,last = 0,len(self.T),len(self.T)-1 self.T+=s nc = len(self.nodes) self.nodes += [-1]*(2*len(s)) T=self.T E=self.E nodes=self.nodes Lm1=len(T)-1 for last_char_index in xrange(first,len(T)): c=T[last_char_index] last_parent_node = -1 while 1: parent_node = origin if first>last: if (origin,c) in E: break else: key = origin,T[first] edge_first, edge_last, edge_end = E[key] span = last - first A = edge_first+span m = T[A+1] if m==c: break E[key] = (edge_first, A, nc) nodes[nc] = origin E[nc,m] = (A+1,edge_last,edge_end) parent_node = nc nc+=1 E[parent_node,c] = (last_char_index, Lm1, nc) nc+=1 if last_parent_node>0: nodes[last_parent_node] = parent_node last_parent_node = parent_node if origin==0: first+=1 else: origin = nodes[origin] if first <= last: edge_first,edge_last,edge_end=E[origin,T[first]] span = edge_last-edge_first while span <= last - first: first+=span+1 origin = edge_end if first <= last: edge_first,edge_last,edge_end = E[origin,T[first]] span = edge_last - edge_first if last_parent_node>0: nodes[last_parent_node] = parent_node last+=1 if first <= last: edge_first,edge_last,edge_end=E[origin,T[first]] span = edge_last-edge_first while span <= last - first: first+=span+1 origin = edge_end if first <= last: edge_first,edge_last,edge_end = E[origin,T[first]] span = edge_last - edge_first return self def make_choices(self): """Construct a sorted list for each node of the possible continuing characters""" choices = self.choices = [list() for n in xrange(len(self.nodes))] # Contains set of choices for each node for (origin,c),edge in self.E.items(): choices[origin].append(c) choices=[sorted(s) for s in choices] # should not have any repeats by construction return choices def find_substrings(self,A,term): """Recurses through the tree appending unique substrings into A. Strings assumed to use term as the terminating character""" choices = self.make_choices() def f(node,depth): t=0 for c in choices[node]: if c==term: continue first,last,end = self.E[node,c] # All end points along this edge result in new unique substrings edge_len = last-first+1 a = first-depth for b in range(first,last+1): if self.T[b]!=term: A.append( self.T[a:b+1] ) f(end,depth+edge_len) return t return f(0,0) def fast_find_all_substrings(strings): S = SuffixTree() term = '\0' for string in strings: S.add(string+term) A=[] S.find_substrings(A,term) return A A="abc","abcd","bca" print fast_find_all_substrings(A) 
    Python - лучший язык программирования в мире.