Substring question on mips assembly language

Question

Please help as soon as possible... Write a MIPS assembly language program that prompts the user to input two strings (each should be no longer than 50 characters including the null terminator). Your program should determine whether the second string is a substring of the first. If it is, then your program should print out the first index in which the second string appears in the first. For example, if the first string is “Hello World” and the second string is “lo”, then the program should print out 3, i.e. the starting index of “lo” in “Hello World.” If the second string is not contained in the first string, then your program should print out -1.

Answer 1

To be able to understand what you have to implement at assembly level, the first thing you should do, is understanding the high-level algorithm. Why?

• It's easier for you to see all the cases and edge-cases in time!
• To look back at what have I been trying to do again? in the middle of programming the Assembly version.
• To quickly see which variables you (certainly) need.

I wrote following program (forgive me, python has been a while for me):

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'
    )

I first thought I could optimize the standard solution (is_in_string_2), leaving out the second for-loop (is_in_string_1), but after some thinking I already found out it would fail (the edge-case wasn't even in any of my test-data!) - so I left it as an example for how important it is that you use a correct algorithm.

The program produces the following output:

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

Notice how all output was correct, except for the last line, where the first algorithm is wrong.

Before you continue:

• You have to make your own len() function in MIPS; note that all string are (if I remember correctly) null terminated, so you'll have to count all non-null characters of a string, or in other words, count how many characters precede the null-terminator.
• You should use j, $ra and jr calls to go to a "function" or subroutines. (Search)
• While in one, you can call other functions using the stack. (Search)