String Processing

String Processing

12 questions · Fundamental Engineering

Practice

From the answer group below, select the correct combination of answers to be inserted into A and B in the program. Here, the array indexes start at 1.

The function isIsomorphic compares the two character arrays s1 and s2 that are given as arguments. Both s1 and s2 have one or more elements.
Two character arrays are considered isomorphic if the characters in s1 can be consistently replaced to obtain s2 without changing the order of characters. Each character in s1 must map to exactly one character in s2, and no two characters in s1 may map to the same character in s2. A character may map to itself.

If s1 and s2 do not have the same number of elements, the function returns false. Otherwise, it returns true if s1 and s2 are isomorphic and false if they are not.

The table lists examples of s1 and s2 given to the function isIsomorphic and the return values.

Table Examples of s1 and s2 given to the function isIsomorphic and the return values

s1s2Return Value
{"e", "g", "g"}{"a", "d", "d"}true
{"f", "o", "o"}{"b", "a", "r"}false
{"p", "a", "p", "e", "r"}{"t", "i", "t", "l", "e"}true
{"a", "b"}{"c", "c"}false
[Program]
○ boolean: isIsomorphic(character []: s1, character []: s2)
integer: len, i, j
len ← number of elements in s1
if (number of elements in s2 ≠ len)
return false
endif
for (increase i from 1 to (len - 1) by 1)
for (increase j from (i + 1) to len by 1)
if ((s1[i] = s1[j] and A)
or (s1[i] ≠ s1[j] and B))
return false
endif
endfor
endfor
return true

Answer group

OptionAB

From the answer group below, select the correct answer to be inserted into blank in the program. Here, the array indexes start at 1.

The function extractEmails receives text as an argument, extracts email addresses from the text, and returns all collected email addresses. Here, a string in the format “name@domain” is considered to be an email address, where “name” and “domain” comprise only alphanumeric characters and the characters “.” (dot), “_” (underscore), and “-” (hyphen-minus). The table shows the description of the functions used in the function extractEmails.

Table Functions used in the function extractEmails

FunctionReturn valueDescription
findSubstring(string: str,string: substr,integer: start)integerReturns the position of the first occurrence of the substring substr in the string str, starting from the position start. If the substring is not found, it returns 0.
getChar(string: str,integer: index)characterReturns the character at the position specified by index in the string str.
length(string: str)integerReturns the length of the string str.

extractEmails("Contact us at john.doe@example.com or jane_smith@test.org for support.") returns {"john.doe@example.com", "jane_smith@test.org"}. In addition, extractEmails("a@b@c") returns {"a@b", "b@c"}.

[Program]
○ string []: extractEmails(string: txt)
character []: validChars ← {alphanumeric characters, ".", "_", "-"}
string []: results ← {}
integer: index ← 1
integer: atIndex, i, count
string: candidate
while (true)
atIndex ← findSubstring(txt, "@", index)
if (atIndex = 0)
exit the while block
endif
candidate ← ""
for (blank by 1)
if (getChar(txt, i) exists in validChars)
prepend getChar(txt, i) to candidate
else
exit the for block
endif
endfor
count ← 0
if (length(candidate) > 0)
append "@" to candidate
for (increase i from atIndex + 1 to length(txt) by 1)
if (getChar(txt, i) exists in validChars)
append getChar(txt, i) to candidate
count ← count + 1
else
exit the for block
endif
endfor
if (count > 0)
append the value of candidate at the end of results
endif
endif
index ← atIndex + 1
endwhile
return results

Answer group

From the answer group below, select the correct combination of answers to be inserted into A and B in the program. Here, the array index starts at 1.

The function containsSubstring receives two-character arrays str and seq as arguments, and returns a boolean value indicating whether the character array str contains the sequence seq as a substring. The character array str contains seq as a substring if every sequence of consecutive characters in seq exists somewhere in the sequence of characters in str, in the same order. For example, containsSubstring({"a", "p", "p", "l", "e"}, {"p", "l", "e"}) returns true, and containsSubstring({"a", "p", "p", "l", "e"}, {"a", "e"}) returns false. Assume that the number of elements in str and seq is one or more.

[Program]
○ boolean: containsSubstring(character []: str, character []: seq)
integer: strlen, seqlen, len, i, j
strlen ← the number of elements in str
seqlen ← the number of elements in seq
if (seqlen > strlen)
return false
endif
len ← strlen - seqlen + 1
for (increase i from 1 to len by 1)
j ← 1
while (j ≤ seqlen)
if (A ≠ seq[j])
exit the while block
endif
j ← j + 1
endwhile
if (B)
return true
endif
endfor
return false

Answer group

OptionAB

From the answer group below, select the correct answer to be inserted into blank in the program. Here, the array index starts at 1.

The function hammingDistance compares the two-character arrays s1 and s2 that are given as arguments. s1 and s2 have one or more elements. If s1 and s2 do not have the same number of elements, the function returns -1. Otherwise, it returns the number of indices where two arrays have different element values at the same index. The figure shows an example of two character arrays. APPLE and APRIE have different element values at two indices.

APPLEAPRIE

Figure Example of two-character arrays

The table lists examples of s1 and s2 given to the function hammingDistance and the return values. In the program, areas outside of the arrays must not be referenced.

Table Examples of s1 and s2 given to the function hammingDistance and the return values

s1s2Return value
{"a", "p", "p", "l", "e"}{"a", "p", "p", "l", "e"}0
{"a", "p", "p", "l", "e"}{"a", "p", "r", "i", "l"}3
{"a", "p", "p", "l", "e"}{"m", "e", "l", "o", "n"}5
{"a", "p", "p", "l", "e"}{"p", "i", "e"}-1
[Program]
○ integer: hammingDistance(character []: s1, character []: s2)
integer: i, cnt ← 0
if (the number of elements in s1 ≠ the number of elements in s2)
return -1
endif
for (increase i from 1 to the number of elements in s1 by 1)
if (blank)
cnt ← cnt + 1
endif
endfor
return cnt

Answer group

From the answer group below, select the correct combination of answers to be inserted into A and B in the program.

Given two strings, str1 and str2, the task is to determine the length of the longest common subsequence (LCS), that is, the length of the longest subsequence present in both strings. For instance, if str1 is “ABXDZ” and str2 is “ABCD”, the LCS between str1 and str2 will be “ABD” and the length of the LCS will be 3.
The function lcs(string: str1, string: str2, integer: m, integer: n) takes two strings str1 and str2 and two integers m and n as arguments. str1 and str2 are the strings on which the length of the LCS is calculated. m and n are indexes addressing the target characters in str1 and str2, respectively. On the first call, m and n represent the lengths of str1 and str2, respectively. The function returns an integer containing the value of the length of the LCS of str1 and str2. For instance, the function may be called as lcs("ABXDZ", "ABCD", 5, 4).

Another function max(integer: a, integer: b) is also used. The function takes two integers a and b as arguments. It compares these two integers and returns the integer value of whichever is the maximum between a and b.

[Program]
○ integer: max(integer: a, integer: b)
if (a > b)
return a
else
return b
endif
○ integer: lcs(string: str1, string: str2, integer: m, integer: n)
if (m = 0 or n = 0)
return 0
endif
if (the m-th character of string str1 = the n-th character of string str2)
return 1 + lcs(str1, str2, m - 1, n - 1)
else
return max(lcs(str1, str2, m, A),
lcs(str1, str2, m - 1, B))
endif

Answer group

OptionAB

From the answer group below, select the correct combination of answers to be inserted into A and B in the program. Here, the array index starts at 1.

The function isPalindrome determines whether the character array s given as argument is a palindrome. Palindromes are words when read backward will still be the same such as “noon” and “madam.”
If character array s is a palindrome, it returns the value true and if not, the function returns false.

The table lists examples of s given to the function isPalindrome and the return values. In the program, areas outside of the arrays must not be referenced.

Table Examples of s given to the function isPalindrome and the return values

sReturn value
{"n", "o", "o", "n"}true
{"n", "i", "g", "h", "t"}false
{"m", "a", "d", "a", "m"}true
{"s", "i", "r"}false
[Program]
○ boolean: isPalindrome(character []: s)
integer: left ← 1
integer: right ← the number of elements in s
boolean: ok ← true
while (left < right)
if (A)
left ← left + 1
B
else
ok ← false
break
endif
endwhile
return ok

Answer group

OptionAB

From the answer group below, select the correct combination of answers to be inserted into A through C in the program.

Function hammingDistance receives two strings as argument and returns Hamming distance as the return value. Hamming distance is a metric used to measure the difference between two strings of equal length. It counts the number of positions at which the corresponding characters are different. For instance, the return value is 2 when the function hammingDistance("101010", "111000") is called, because positions 2 and 5 have different characters.
It can also be extended to strings of different lengths by considering the unmatched characters as differences. For instance, the return value is 5 when the function hammingDistance("101010", "111000111") is called, because of two differences in first six characters and addition of three extra unmatched characters.

[Program]
○ integer: hammingDistance(string: s1, string: s2)
integer: distance, length1, length2, minLength, remainingLength
length1 ← length of s1
length2 ← length of s2
distance ← 0
minLength ← length1
if (A)
minLength ← length2
endif
for (increase i from 1 to minLength by 1)
if (the i-th character of string s1 B the i-th character of string s2)
distance ← distance + 1
endif
endfor
if (length1 > length2)
remainingLength = length1 - length2
else
remainingLength = length2 - length1
endif
distance ← C
return distance

Answer group

OptionABC

From the answer group below, select the correct answer to be inserted into blank in the program.

A string of character(s) is called a palindrome if it reads the same forwards and backwards. Here the input string consists of only the uppercase Roman alphabet. As an example, the string "MADAM" is a palindrome as it remains the same when written backwards (right to left). The procedure isPalindrome receives a string str as a parameter and outputs whether the string str is a palindrome or not. The procedure should use the minimum number of iterations for any number of characters in the string. Note that division is performed for data type integer, that is, a ÷ b is the quotient of a divided by b.

[Program]
○isPalindrome(string: str)
integer: i, j, len
boolean: flag
flag ← true
len ← number of characters in str
i ← 1
j ← len
while (blank)
if (the i-th character of string str ≠ the j-th character of string str)
flag ← false
exit the while block
endif
i ← i + 1
j ← j - 1
endwhile
if (flag)
output str, " is a palindrome."
else
output str, " is not a palindrome."
endif

Answer group

From the answer group below, select the correct combination of answers to be inserted into A and B in the program. Here, the array index starts at 1.

N-grams are continuous sequences of words, symbols, or tokens in a document. N-grams of texts are extensively used in text mining and natural language processing tasks. An n-gram model is built by counting how often word sequences occur in corpus text and then estimating the probabilities. The figure shows an example of the unigrams, bigrams, and trigrams of the example sentence “ITPEC includes members from 6 countries.”

unigramITPECincludesmembersfrom6countriesbigramITPEC includesincludes membersmembers fromfrom 66 countriestrigramITPEC includes membersincludes members frommembers from 6from 6 countries

Figure Example of unigrams, bigrams, and trigrams

The procedure NGRAMS generates n-grams from text and outputs them. If the argument for n is 1, the procedure outputs the unigram result. If n is 2, the procedure outputs the bigram result and so on. The input text is a string of words separated by a space, so it is needed to split the string to generate n-grams. The table shows the description of the functions used in the program. In this question, the operator “+” is used for both arithmetic calculation of integer data type and concatenation of one or more strings into one string. In the program, areas outside of the array must not be referenced.

Table Functions

FunctionReturn valueDescription
split(string: str)string []Returns the words that are separated with a space in the text str
[Program]
○ NGRAMS(integer: n, string: text)
string []: words ← split(text)
string: s
integer: i, j, length
length ← the number of elements in words
for (increase i from 1 to (A) by 1)
s ← ""
for (increase j from i to (B) by 1)
s ← s + words[j] + " "
endfor
output s
endfor

Answer group

OptionAB

From the answer group below, select the correct answer to be inserted into blank in the program. Here, the array index starts at 1.

The function simRatio compares the two character-type arrays s1 and s2, each with one or more elements, that are given as arguments, and if their numbers of elements are equal, returns (the number of pairs of elements with the same index whose characters match ÷ the number of elements in s1) as a real number, as an index of how similar the sequences of the arrays are. For example, the return value is 1 when all elements of the arrays match, and 0 when none of the elements match.
If the numbers of elements of the two arrays are not equal, the function returns −1.

The table shows examples of s1 and s2 given to the function simRatio and the return values. In the program, areas outside the arrays must not be referenced.

Table Examples of s1 and s2 given to the function simRatio and the return values

s1s2Return value
{"a", "p", "p", "l", "e"}{"a", "p", "p", "l", "e"}1
{"a", "p", "p", "l", "e"}{"a", "p", "r", "i", "l"}0.4
{"a", "p", "p", "l", "e"}{"m", "e", "l", "o", "n"}0
{"a", "p", "p", "l", "e"}{"p", "e", "n"}-1
[Program]
○ real: simRatio(character []: s1, character []: s2)
integer: i, cnt ← 0
if (the number of elements in s1 ≠ the number of elements in s2)
return -1
endif
for (increase i from 1 to the number of elements in s1 by 1)
if (blank)
cnt ← cnt + 1
endif
endfor
return cnt ÷ the number of elements in s1 /* calculated as real numbers */

Answer group

From the answer group below, select the correct answer to be inserted into blank in the program.

This is a program that, for any two different characters c1 and c2, calculates the ratio at which c2 appears immediately after c1 in the English words contained in a group of English words. English words consist of lowercase English letters only. When the last character of an English word is c1, that position is not included in the calculation of the ratio. For example, in the group of English words consisting of the four English words “importance,” “inflation,” “information,” and “innovation” shown in the figure, let c1 be “n” and c2 be “f”. Other than the last characters of the English words, there are five “n”s, and of these, two have “f” as the next character. Therefore, the ratio to be calculated is 2 ÷ 5 = 0.4. When the sequence of c1 and c2 never appears, the ratio is defined as 0 regardless of the number of occurrences of c1.

importanceThe nextcharacter is “c”inflationThe nextcharacter is “f”informationThe nextcharacter is “f”innovationThe nextcharacter is “n”The nextcharacter is “o”Not included inthe calculationof the ratio

Figure Example of a group of English words consisting of four words

In the program, the group of English words is stored in the Words-type global variable words. The table shows an explanation of the methods of the class Words. In this question, the operator “+” for strings represents the concatenation of strings. Also, the operator “÷” for integers performs the calculation as real numbers.

Table Explanation of the methods of the class Words

MethodReturn valueDescription
freq(string: str)integerReturns the number of occurrences of the string str in the group of English words.
freqE(string: str)integerReturns the number of English words that end with the string str in the group of English words.
[Program]
global: Words: words /* stores the group of English words */
/* returns the ratio at which c2 appears immediately after c1 */
○ real: prob(character: c1, character: c2)
string: s1 ← a string consisting only of the one character c1
string: s2 ← a string consisting only of the one character c2
if (words.freq(s1 + s2) is greater than 0)
return blank
else
return 0
endif

Answer group

From the answer group below, select the correct answer to be inserted into blank in the description. Here, the array index starts at 1.

The function search receives two character-type arrays as the arguments data and key respectively, searches data for all the sequences that are the same as the sequence of the elements of key, and returns an array that stores all the indexes of the first elements of those sequences. If none is found, it returns an array with 0 elements.
When the function search is called as search({"a", "b", "a", "b", "c", "a", "b", "c"}, {"a", "b", "c"}), the number of times the conditional expression on the line /*** β ***/ is true is blank.

[Program]
/* key is an array with one or more elements */
○ integer []: search(character []: data, character []: key)
integer: i, j, lenData, lenKey
integer []: result ← {} // array with 0 elements
lenData ← the number of elements in data
lenKey ← the number of elements in key
/* The loop is not executed when (lenData - lenKey + 1) is 0 or less */
for (increase i from 1 to (lenData - lenKey + 1) by 1)
for (increase j from 1 to lenKey by 1) // α
if (data[i + j - 1] is equal to key[j]) /*** β ***/
if (j is equal to lenKey)
add the value of i to the end of result
endif
else
exit the for block marked α
endif
endfor
endfor
return result

Answer group