Подстрока вопроса на ассемблере mips - PullRequest
Новая
       133

Подстрока вопроса на ассемблере mips

0 голосов
/ 17 июня 2020

Пожалуйста, помогите как можно скорее ... Напишите программу на языке ассемблера MIPS, предлагающую пользователю ввести две строки (каждая не должна быть длиннее 50 символов, включая нулевой ограничитель). Ваша программа должна определить, является ли вторая строка подстрокой первой. Если это так, ваша программа должна распечатать первый индекс, в котором вторая строка появляется в первой. Например, если первая строка - «Hello World», а вторая - «lo», тогда программа должна распечатать 3, то есть начальный индекс «lo» в «Hello World». Если вторая строка не содержится в первой строке, тогда ваша программа должна распечатать -1.

1 Ответ

0 голосов
/ 18 июня 2020

Чтобы понять, что вам нужно реализовать на уровне сборки, первое, что вам нужно сделать, это понять алгоритм высокого уровня. Почему?

  • Вам легче увидеть все случаи и крайние случаи вовремя!
  • Чтобы вернуться к , что я пытался сделать снова? в середине программирования версии Assembly.
  • Чтобы быстро увидеть, какие переменные вам (конечно) нужны.

Я написал следующую программу (простите меня, python был некоторое время для меня): 

def is_in_string_1(string, substring):
    """
        aaba: a, b, ab, ba, aba (last one will fail)
    """
    length = len(string)
    sublength = len(substring)

    if (sublength == 0):
        return True

    j = 0
    for i in range(0, length):
        if string[i] != substring[j]:
            j = 0
        else:
            j += 1
            if j == sublength:
                return True
    return False

def is_in_string_2(string, substring):
    """
        aaba: a, b, ab, ba, aba
    """
    length = len(string)
    sublength = len(substring)
    for i in range(0, length + 1 - sublength):  # string: aabc; substring: c; length: 4; sublength: 1; indexes: 0,1,2,3;
        is_substring = True
        for j in range(0, sublength):           # for the sake of the algorithm, no slicing here
            if string[i+j] != substring[j]:
                is_substring = False
                break
        if is_substring:
            return True
    return False
 
stringTuples = [
    ("aaa", "aa"),
    ("aaa", "aaa"),
    ("aaa", "aab"),
    ("abc", "bc"),
    ("abc", "a"),
    ("abc", "abc"),
    ("aaa", ""),
    ("aaa", "b")
]

for stringTuple in stringTuples:
    print(
        stringTuple[0],
        stringTuple[1],
        ':',
        is_in_string_1(stringTuple[0], stringTuple[1]),
        is_in_string_2(stringTuple[0], stringTuple[1]),
        sep='\t'
    )

Сначала я подумал, что могу оптимизировать стандартное решение (is_in_string_2), исключив второе for-l oop (is_in_string_1), но после некоторого размышления Я уже узнал, что это не удастся (крайнего случая даже не было ни в одном из моих тестовых данных!), Поэтому я оставил это как пример того, насколько важно, чтобы вы использовали правильный алгоритм.

Программа выдает следующий результат: 

aaa     aa      :       True    True
aaa     aaa     :       True    True
aaa     aab     :       False   False
abc     bc      :       True    True
abc     a       :       True    True
abc     abc     :       True    True
aaa             :       True    True
aaa     b       :       False   False
aaba    aba     :       False   True

Обратите внимание, что весь вывод был правильным, за исключением последней строки, где первый алгоритм неверен.

Перед тем, как продолжить:

  • Вы должны сделать свою len() функцию в MIPS; обратите внимание, что вся строка (если я правильно помню) завершается нулем, поэтому вам придется подсчитать все ненулевые символы строки или, другими словами, подсчитать, сколько символов предшествует нулевому ограничителю.
  • Вы должны использовать j, $ra и jr вызовы go «функции» или подпрограмм . (Поиск)
  • Находясь в одном, вы можете вызывать другие функции , используя стек . (Поиск)
...