You are given two strings S and T , each n characters long. You have to establis
ID: 3739464 • Letter: Y
Question
You are given two strings S and T , each n characters long. You have to establish whether one of them is a right cyclic shift of the other. For example, PLEA is a right cyclic shift of LEAP, and vice versa. (Formally, T is a right cyclic shift of S if T can be obtained by concatenating the (n ? i)-character suffix of S and the i-character prefix of S for some 1? i ? n.) a. Design a space-efficient algorithm for the task. Indicate the space and time efficiencies of your algorithm.
b. Design a time-efficient algorithm for the task. Indicate the time and space efficiencies of your algorithm.
7.Explain how to use hashing to check whether all elements of a list are distinct.
What is the time efficiency of this application? Compare its efficiency with
that of the brute-force algorithm (Section 2.3) and of the presorting-based
algorithm (Section 6.1).
Explanation / Answer
Answer(a): Space efficient algorithm
Algorithm rightShift(S,T,n)
{
//starting char of T can have index 0 to n-1 in S
for( i=0 to n-1){
//start matching charater wise T and S(n characters from index i)
bool flag=true; //mark flag false when not matched, else will remain true
for(j=i;j<n+i;j++){
if(S[j%n]!=T[j-i])
{ flag=false; break; }
}
if(flag==true) return true; //if T is matched by a cyclic shift of S then return true
}
//when not matched by any value of i then return false
return false;
}
Space complexity: O(1) //no extra space
Time complexity: O(n^2) //two nested loops each running n times
Answer(b): Time efficient algorithm
We can create a string temp = S+S; //concatenate string S with S at the end
and find patter T in temp, if found return true else false.
Now the time complexity depends on algorithm used for pattern matching.
We will use KMP search algorithm which runs in linear time.
Algorithm rightShift(S,T,n){
temp = S + S; //concatenate S with S
bool flag = KmpSearch(T,temp); //T is pattern and temp is text
return flag;
}
Algorithm KmpSearch(pat,txt)
{
m = pat.size();
n= txt.size();
lps[] // create lps[]
//lps[i] is the longest proper prefix which is also proper suffix of pat[0...i]
//proper suffix means the whole string as a suffix is not considered.
// Preprocess the pattern (calculate lps[] array)
lps = computeLPS(pat, m);
i = 0; // index for txt[]
j = 0; // index for pat[]
while (i < n)
{
if (pat[j] == txt[i])
{
j++;
i++;
}
if (j == m) //matched char is the last char of the pattern
{
return true; //return as soon as first match of pat in txt is found
}
else if (i < n && pat[j] != txt[i]) // mismatch after j matches
{
// Do not match lps[0..lps[j-1]] characters,
// they will match anyway
if (j != 0)
j = lps[j-1];
else //if j=0, i.e. first character is not matching then move i one character ahead for new search
i = i+1;
}
}
return false; //not matched
}
//cpmpute LPS array
//For the pattern “AABAACAABAA”, m=11
//pat[0..0] = there is no proper longest prefix suffix (you may think that A is longest prefix suffix but it not proper)
//pat[0..1] = proper longest prefix suffix is A of length 1
//pat[0..2] = there is no proper longest prefix suffix
//pat[0..3] = proper longest prefix suffix is A of length 1
//pat[0..4] = proper longest prefix suffix is AA of length 2
//pat[0..5] = there is no proper longest prefix suffix
//pat[0..6] = proper longest prefix suffix is A of length 1
//pat[0..7] = proper longest prefix suffix is AA of length 2
//pat[0..8] = proper longest prefix suffix is AAB of length 3
//pat[0..9] = proper longest prefix suffix is AABA of length 4
//pat[0..10] = proper longest prefix suffix is AABAA of length 5
//lps[] is [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]
Algorithm computeLPS(pat, m)
{
lps[]; //create an array lps
// length of the previous longest prefix suffix
len = 0;
lps[0] = 0; // lps[0] is always 0 because length of subpattern is 1 and cannot be have proper lps
// the loop calculates lps[i] for i = 1 to m-1
i = 1; //initialise i by 1
while (i < m)
{
if (pat[i] == pat[len]) //check if current character is same as (len+1)th character of pat
{
len++; //current longest lps will be len+1
lps[i] = len;
i++;
}
else //not matched
{
// Observe carefully.
//Consider the example.
// AAACAAAA . The idea is similar to search step.
//len=3 (AAA) and i=7(last char)
//
if (len != 0)
{
len = lps[len-1]; //set len = lps of the (len)th character of pat, e.g here the 3rd character, i.e. len = lps[2] = 2
// Also you should not increment i here because you have not assigned lps[i] yet
}
else // if previous len is 0
{
lps[i] = 0; //current lps will also be 0
i++;
}
}
}
return lps; //return array
}
Space complexity:
for temporary string = 2n = O(n)
for lps array = size of pattern = n = O(n)
total space = O(n)
Time complexity:
the heart of rightShift algorithm is KmpSearch algorithm which takes O(m+n) time inside the while loop
and computeLPS algorithm takes O(m) time for pattern on length m.
Total time by KmpSearch is O(2m+n) = O(n+m)
Now pattern here is n and text(temp string) is 2n
So KmpSearch takes O(n+2n) = O(3n) = O(n)
thus rightShift takes O(n)
Answer(7):
Algorithm distinct_hash(array,n)
{
//find minimum element in array
min = INT_MAX
for(i=0;i<n;i++){
if(array[i]<min)
min=array[i];
}
//find maximum element
max = INT_MIN
for(i=0;i<n;i++){
if(array[i]>max)
max=array[i];
}
//create hash array of size max-min+1
//hashing function will be h(x) = x-min
hash[max-min+1] = {0}; //initialise count of each element with 0
for(i=0;i<n;i++){
hash[array[i]-min]++; //increment the count of current element
}
//loop through hash array and check if each value should be 0 or 1,
//if any element is 2 it means count of some element is more than 1,
//thus all elements are not distinct, return false
for(i=0;i<n;i++){
if(hash[array[i]-min]>1) return false;
}
return true;
}
Time Complexity:
O(n) for finding max and min
O(n) for marking count in hash[] for each element of array
O(n) for checking count of each element of array
total complexity: O(3n) = O(n)
Comparison with brute force approach:
In brute force, we run a loop of each element of the array to match it with any other element, if it is matched return false, else return true.
Time complexity: O(n^2)
hashing algorithm is better than brute force but takes O(max-min+1) space complexity.
Comparison with pre-sorting algorithm:
In this algorithm, we first sort the array and check if two adjacent elements are same. If any two adjacent elements are found to be same return false, else true.
Time complexity: O(nlogn) for sorting and O(n) for checking adjacent elements. Overall time= O(nlogn)+O(n) = O(nlogn)
This takes more time than hashing and less than brute force.This Doesn't take any extra space.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.