Which of the following statements best describes dynamic programming in the context of string processing?
What is the purpose of using string hashing in string processing algorithms?
1 Crore+ students have signed up on EduRev. Have you? Download the App |
Which of the following string processing algorithms is used for exact string matching in a text?
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?