If the patternmatching problem was changed to only find the

If the pattern-matching problem was changed to only find the first instance of a pattern of length m in the text of length n. Describe the data that would cause the worst-case performance and the performance in terms of n Use \"Big-O\" notation, e.g. (n), (n^2), etc. Describe the data that would cause the best-case performance and the performance in terms of n. Use \"Big-O\" notation, e.g. (n), (n^2), etc.

Solution

The object of string searching is to find the location of a specific text pattern within a larger body of text.

if you consider normal brute-force algorithm, which is algorithm that compares the pattern to the text, one character at a time, until unmatching characters are found.The algorithm can be designed to stop on either the first occurrence of the pattern, or upon reaching the end of the text.

Brute Force Pseudo-Code

do

   if

      (text letter == pattern letter)

       compare next letter of pattern to next letter of text

   else

       move pattern down text by one letter

while(entire pattern found or end of text)

For exmaple consider string=\"AAAAAAAAAAAAAAAAAAAAAAAAAAAH\" , pattern=\"AAAAH\"

1)AAAAAAAAAAAAAAAAAAAAAAAAAAAH

   AAAAH 5 comparisons made

2)AAAAAAAAAAAAAAAAAAAAAAAAAAAH

     AAAAH 5 comparisons made

3)AAAAAAAAAAAAAAAAAAAAAAAAAAAH

          AAAAH 5 comparisons made

4)AAAAAAAAAAAAAAAAAAAAAAAAAAAH

             AAAAH 5 comparisons made

5)AAAAAAAAAAAAAAAAAAAAAAAAAAAH

              AAAAH 5 comparisons made

....

N)AAAAAAAAAAAAAAAAAAAAAAAAAAAH

5 comparisons made                 AAAAH

Total number of comparisons: M (N-M+1)

Worst case time complexity: (MN)

if pattern =\"AAAA\"

1)AAAAAAAAAAAAAAAAAAAAAAAAAAAH

   AAAA 5 comparisons made

Total number of comparisons: M

Best case time complexity: (M)