Trying to understand how this text search algorithm flows: I need someone to ste

Question

Trying to understand how this text search algorithm flows:

I need someone to step me through the process of how this works:

input: p(indexed from 1 to m), m, t(indexed from 1 to n), n

output: i

text_search(p,m,t,n){

for i = 1 to n - m + 1 {

j = 1

// i is the index in t of the first character of the substring
// to compare with p, and j is the index in p

// the while loop compares ti...ti+m-1 and p1... pm
    while(ti+j-1== pj) {              j = j + 1                if( j > m)                    return i             }      } return 0 } So what would it return if I had the text "balalaika" and I wanted to find "lai" in the text? Trying to understand how this text search algorithm flows:

I need someone to step me through the process of how this works:

input: p(indexed from 1 to m), m, t(indexed from 1 to n), n

output: i

text_search(p,m,t,n){

for i = 1 to n - m + 1 {

j = 1

// i is the index in t of the first character of the substring
// to compare with p, and j is the index in p

// the while loop compares ti...ti+m-1 and p1... pm
    while(ti+j-1== pj) {              j = j + 1                if( j > m)                    return i             }      } return 0 } So what would it return if I had the text "balalaika" and I wanted to find "lai" in the text?

Explanation / Answer

Dear.. This algorithm searchs for an occurence of the pattern P in text t. it returns the smallest index i such that p occurs in t starting at index i. if p does not occurs in t, it returns 0. Here given text t which is a word processor document. it is first occurrence of pattren p in t which is first occurrence of string p and index characters in t string at 1. Now search for p, to check whether p occurrence at index 1 in t. It stops the first occurrence of p in t. Otherwise check whether p occurrence at index 2 in t. then stop to findthe first occurrence of p in t. then check for p occurs at index 3 in t. and so on.. In this algorithm, i marks the index in t of the first character of the substring to compare with p. This algorithm first tries to i=1; then I = 2, and so on.. Index n-m+1 is the last possible value for I since at this point. The string tn-m+1tn-m+2 …..tm. has length exactly m. If the value of i is set, then . while loop compares ti…..ti+m-1 and p1….pm. If the character match ti+j-1 ==pi. If j is incremented, then I = j+1 and the next characteris compared. If all m characters have matched then found at index I in t. then returns I; means if ( j > m) return i

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.