Блог

У меня предстоящий экзамен, и я пытаюсь пересмотреть. Я наткнулся на этот вопрос, и я застрял в том, как мне поступить. Вопрос заключается в следующем:

Учитывая функцию build_from_substrings(S,T), если вы можете построить T из подстрок S, функция должна вернуть кортеж, содержащий первый и последний индексы подстрок, используемых для построения T. Например, «bcc» создается из индексов (2,4) из «abbcc». Если подстрока не может быть создана, функция возвращает false .

build_from_substrings должен выполняться в O(N ^ 2 M), где:

1. N — количество символов в S
2. M — длина T

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

Это то, что я пробовал.

 class Node:
    def __init__(self,level = None,size = 27,data = None):
        self.link = [None] * size
        self.level = level
        self.data = data
        self.end = False

class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self,key,data):
        level = 0
        current = self.root
        for char in key:
            index = ord(char) - 97   1
            if current.link[index] is not None:
                current = current.link[index]
            else:
                current.link[index] = Node(level=level)
                current = current.link[index]
            level  = 1
        index = 0
        if current.link[index] is not None:
            current = current.link[index]
        else:
            current.link[index] = Node(level=level)
            current = current.link[index]
        current.data = data

    def search(self,key):
        current = self.root
        for char in key:
            index = ord(char) - 97   1
            if current.link[index] is not None:
                current = current.link[index]
            else:
                return False
        index = 0
        if current.link[index] is not None:
            current = current.link[index]
            return current.data
        else:
            return False

def build_from_substring(S,T):
    suffix_trie = Trie()
    length = len(S)
    for i in range(len(S)):
        list = [i,0]
        word = ""
        word  = S[i]
        if i == length-1:
            list[1] = i
        for j in range(i 1,length):
            word  = S[j]
            list[1] = length-1
        suffix_trie.insert(word,list)
 

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

 class Trie:
    def __init__(self):
        self.root = {}
        self.end = '*'

    def insert(self,word):
        '''Traverses the string and inserts each character into the Trie'''
        current = self.root
        for char in word:
            if char not in current:
                current[char] = {}
            current = current[char]
        current[self.end] = self.end

    def search(self,word):
        '''Returns True if word is in the Trie and False if the word is not in the Trie. The search word must not be a substring in the Trie.'''
        current = self.root
        for char in word:
            if char not in current:
                return False
            current = current[char]
        return True if self.end in current else False
 

Затем установил некоторые случаи, когда нужно возвращать пару индексов, а когда возвращать False.

 trie = Trie()
trie.insert('word')
build_from_substrings('have you heard the word in the worlds.', trie)
(19, 22)
build_from_substrings('have these words today.', trie)
(11, 14)
build_from_substrings('have you heard.', trie)
False
 

Пройдите по входной строке и, если в дереве есть совпадение, отметьте индекс. Если они совпадают до тех пор, пока слово в дереве не будет завершено, уцените конечный индекс и верните. Если они не совпадают при обходе строки, верните False .

 def build_from_substrings(string,trie):
    current = trie.root
    start = None
    end = None
    for idx, char in enumerate(string):
        if char in current:
            if start is None:
            '''recored the starting index where they first match'''
                start = idx
            current = current[char]
        elif start and trie.end in current:
        '''If start is not none and our Trie has an end symbol we have reached a word'''
            return (start,idx-1)
        else:
        '''if the character(char) is not in current then we need to start over by resetting "current" value and "start" value'''
            current = trie.root
            start = None
    if start is None or trie.end not in current:
    '''If our start value is None or there is no end symbol then that means we have no substrings to report'''
        return False
    return (start,end) if end else (start,len(string)-1)