Блог

В настоящее время я застрял в попытке создать наивный алгоритм, который, учитывая фрагмент шаблона, например aabba, ищет его в тексте, например abbbbaababaabbaabbaabbaa по одной букве за раз. Он сравнит a с текстом, если это правильно, затем сравнивает следующую букву, и если это неправильно, весь шаблон сдвинется на единицу и сравнит a с b и т.д.

мы приводили пример кода

 print "Input text: ",
text = raw_input()
print "Input pattern: ",
pattern = raw_input()

index = text.find(pattern)
while index > -1:
    print index
    index = text.find(pattern, index 1)
  

но функция find () в python слишком быстрая (мне нужен неоптимизированный алгоритм, использующий while
и для операторов loops, я думаю).

Любая помощь приветствуется, спасибо

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

 def my_find(text, pattern):
    '''Find the start index of a pattern string in a text.
    Return -1 if not found, and assume that pattern is not empty'''

    found = False
    current_start_index = text.find(pattern[0])
    index_text = current_start_index
    index_pattern = 0

    while not found and index_text   len(pattern) - 1 < len(text) and 
            current_start_index != -1:

        index_text  = 1
        index_pattern  = 1

        while index_text < len(text) and 
                index_pattern < len(pattern) and 
                text[index_text] == pattern[index_pattern]:

            if index_pattern == len(pattern) - 1:
                found = True
                break
            else:
                index_text  = 1
                index_pattern  = 1

        if not found:
            current_start_index = text.find(pattern[0],current_start_index   1)
            index_text = current_start_index

    if found:
        return current_start_index
    else:
        -1
  

 def my_find(haystack, needle):
    n_len = len(needle)
    start = 0
    while start <= (len(haystack)-n_len 1):
        if haystack[start:start n_len-1] == needle:
            return True
        start  = 1
  

Это, насколько я могу понять, ваш алгоритм. Не тестировалось, протестируем и сообщим вам, работает ли это.

Протестировано и, похоже, работает.

Похоже, вы изучаете регулярные выражения, вот фрагмент, который может помочь вам начать.

 myFileName = "abbababaaa"
patternToMatch = "ababa"

i = 0
j = 0
while (i < len(myFileName)):
    if (patternToMatch[i:i] == myFileName[j:j]):
        i  
        j  
    else:
        i = 0        

if len(patternToMatch) == i:
    # matched a pattern