Test: String Processing - 1 - Software Development MCQ

Which of the following statements is true regarding the Rabin-Karp algorithm?

What is the main idea behind the KMP (Knuth-Morris-Pratt) algorithm?

Consider the following Python code:

def longest_common_subsequence(s1, s2):
    m = len(s1)
    n = len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

s1 = "ABCBDAB"
s2 = "BDCAB"
print(longest_common_subsequence(s1, s2))

What will be the output of the code?

Consider the following Python code:

def string_matching(pattern, text):
    m = len(pattern)
    n = len(text)
    for i in range(n - m + 1):
        j = 0
        while j < m and text[i + j] == pattern[j]:
            j += 1
        if j == m:
            return True
    return False

pattern = "abc"
text = "abdefghabcijk"
print(string_matching(pattern, text))
What will be the output of the code?

Consider the following Python code:

def z_function(s):
    n = len(s)
    z = [0] * n
    l = r = 0
    for i in range(1, n):
        if i <= r:
            z[i] = min(r - i + 1, z[i - l])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] - 1 > r:
            l = i
            r = i + z[i] - 1
    return z

s = "ABACABAC"
print(z_function(s))

What will be the output of the code?

Consider the following Python code:

def suffix_array(s):
    suffixes = [(s[i:], i) for i in range(len(s))]
    suffixes.sort()
    return [i for _, i in suffixes]

s = "banana"
print(suffix_array(s))

What will be the output of the code?

Consider the following Python code:

def count_distinct_substrings(s):
    n = len(s)
    distinct_substrings = set()
    for i in range(n):
        for j in range(i, n):
            distinct_substrings.add(s[i:j+1])
    return len(distinct_substrings)

s = "aab"
print(count_distinct_substrings(s))

What will be the output of the code?

Consider the following Python code:

def longest_palindrome_substring(s):
    n = len(s)
    max_len = 1
    start = 0
    for i in range(n):
        for j in range(i, n):
            substring = s[i:j+1]
            if substring == substring[::-1] and len(substring) > max_len:
                max_len = len(substring)
                start = i
    return s[start:start + max_len]

s = "babad"
print(longest_palindrome_substring(s))

What will be the output of the code?

Consider the following Python code:

def distinct_palindromic_substrings(s):
    n = len(s)
    distinct_substrings = set()
    for i in range(n):
        for j in range(i, n):
            substring = s[i:j+1]
            if substring == substring[::-1]:
                distinct_substrings.add(substring)
    return len(distinct_substrings)

s = "ababa"
print(distinct_palindromic_substrings(s))

What will be the output of the code?

Consider the following Python code:

def longest_common_substring(s1, s2):
    m = len(s1)
    n = len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    max_len = 0
    end_index = 0

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                if dp[i][j] > max_len:
                    max_len = dp[i][j]
                    end_index = i

    return s1[end_index - max_len: end_index]

s1 = "OldSite:GeeksforGeeks.org"
s2 = "NewSite:GeeksQuiz.com"
print(longest_common_substring(s1, s2))
What will be the output of the code?

Consider the following Python code:

def shortest_common_supersequence(s1, s2):
    m = len(s1)
    n = len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0:
                dp[i][j] = j
            elif j == 0:
                dp[i][j] = i
            elif s1[i - 1] == s2[j - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1])

    supersequence = ""
    i = m
    j = n
    while i > 0 and j > 0:
        if s1[i - 1] == s2[j - 1]:
            supersequence += s1[i - 1]
            i -= 1
            j -= 1
        elif dp[i - 1][j] < dp[i][j - 1]:
            supersequence += s1[i - 1]
            i -= 1
        else:
            supersequence += s2[j - 1]
            j -= 1

    while i > 0:
        supersequence += s1[i - 1]
        i -= 1

    while j > 0:
        supersequence += s2[j - 1]
        j -= 1

    return supersequence[::-1]

s1 = "AGGTAB"
s2 = "GXTXAYB"
print(shortest_common_supersequence(s1, s2))
What will be the output of the code?

Consider the following Python code:

def distinct_common_subsequences(s1, s2):
    m = len(s1)
    n = len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1]
            else:
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]

    return dp[m][n]

s1 = "abcd"
s2 = "acde"
print(distinct_common_subsequences(s1, s2))

What will be the output of the code?