a. Explain how to use a brute-force algorithm to find the first occurence of a g
ID: 3591611 • Letter: A
Question
a. Explain how to use a brute-force algorithm to find the first occurence of a given string of m characters, called the target, in a string of n characters, where m n, called the text. Hint: Think in terms of finding a match for the first character of the target and checking successive characters for a match, and if they do not all match, moving the start location one character to the right b. Express your algorithm in pseudocode c. Give a big-O estimate for the worst-case time complexity of the brute-force algorithm you described.Explanation / Answer
Match(String source, String target,int m,int n)
1. {
2. source_position=1,target_position=1 //beginning with first index of source and target string. All index starts from 1
3. while(target_position<=n-m+1) /*the loop will execute till the target string has the possibility of having source as substring*/
4. while ((source[source_position]==target[target_position+source_position-1]) and (source_position<=m)) /*the loop will execute till the matching is there*/
5. if(source_position==m ) // if we reach the end of source string, it means we have found the match
6. then print "target string is substring of source string" // We will print the message and return
7. exit
8. endif
9. source_position=source_position+1 // incrementing each time source index by 1
10. end_while //end of innermost while loop
11. target_position=target_position+1 //if the source string not matched with target string, we increment target_position index by 1
12. source_position=1 //again we will start from first index of source string for next iteration of innermost loop
13. end_while //end of outermost while loop
14. print "target string is not substring of source string" //if we don't get match within outermost loop, it means we didn't find match
15. exit
16. }
pseudo code in C is described below:-
void Match(char source[],char target[],int m,int n)
{
int source_position=0, target_position=0; //beginning with first index of source and target string. All index starts from 0
while(target_position<n-m+1) /*the loop will execute till the target string has the possibility of having source as substring*/
{
while((source[source_position]==target[target_position+source_position])&&(source_position<m)) /*the loop will execute till the matching is there*/
{
if(source_position==m-1) // if we reach the end of source string, it means we have found the match, index will end at m-1
{
printf("String is matched"); // We will print the message and return
return;
}
source_position = source_position+1; // incrementing each time source index by 1
}
target_position = target_position+1; //if the source string not matched with target string, we increment target_position index by 1
source_position = 0; //again we will start from first index of source string for next iteration of innermost loop
}
printf("Source string does not contain target string"); //print the unsuccessful message
return;
}
Worst case happen, when for every iteration of outermost loop, innermost loop goes till m iteration and in last iteration of innermost loop, it find
unsuccessful match. There will be maximum of n-m+1 iterations of outermost loop, when it does not find successful match.
Worst case complexity = O((n-m+1)*m) = O(mn)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.