String Pattern Search

1.String Pattern Search: Naive Algorithm:
Given a text txt[0..n-1] and a pattern pat[0..m-1], write a function search(char pat[], char txt[]) that prints all occurrences of pat[] in txt[]. You may assume that n > m.
Examples:
1) Input:

txt[] =  "THIS IS A TEST TEXT"
  pat[] = "TEST"

Output:
Pattern found at index 10
2) Input:

txt[] =  "AABAACAADAABAAABAA"
  pat[] = "AABA"

Output:

Pattern found at index 0
   Pattern found at index 9
   Pattern found at index 13

http://www.geeksforgeeks.org/searching-for-patterns-set-1-naive-pattern-searching/

2.String Pattern Search-II  -- Rabin Karp Algorithm:


uses an hashing function;
preprocessing phase in O(m) time complexity and constant space;
searching phase in O(mn) time complexity;
O(n+m) expected running time.


Instead of checking at each position of the text if the pattern occurs or not, it is better to check first if the contents of the current string "window" looks like the pattern or not. In order to check the resemblance between these two patterns, a hashing function is used.


Hashing a string involves computing a numerical value from the value of its characters using a hash function. The Rabin-Karp method uses the rule that if two strings are equal, their hash values must also be equal. Note that the converse of this statement is not always true, but a good hash function tries to reduce the number of such hash collisions.


Rabin-Karp computes hash value of the pattern, and then goes through the string computing hash values of all of its substrings and checking if the pattern's hash value is equal to the substring hash value, and advancing by 1 character every time. If the two hash values are the same, then the algorithm verifies if the two string really are equal, rather than this being a fluke of the hashing scheme. It uses regular string comparison for this final check.



Rabin-Karp is an algorithm of choice for multiple pattern search. If we want to find any of a large number, say k, fixed length patterns in a text, a variant Rabin-Karp that uses a hash table to check whether the hash of a given string belongs to a set of hash values of patterns we are looking for. Other algorithms can search for a single pattern in time order O(n), hence they will search for k patterns in time order O(n*k). The variant Rabin-Karp will still work in time order O(n) in the best and average case because a hash table allows to check whether or not substring hash equals any of the pattern hashes in time order of O(1).





http://www.geeksforgeeks.org/searching-for-patterns-set-3-rabin-karp-algorithm/

3.String Pattern Search-III  -- KMP Algorithm: Given a text txt[0..n-1] and a pattern pat[0..m-1], write a function search(char pat[], char txt[]) that prints all occurrences of pat[] in txt[]. You may assume that n > m.  Input: txt[] = "AABAACAADAABAAABAA" pat[] = "AABA" Output: Pattern found at index 0 Pattern found at index 9 Pattern found at index 13 http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/ Strategy: The Naive pattern searching algorithm [with a worst case complexity of O(m(n-m+1))] doesn't work well in cases where we see many matching characters followed by a mismatching character. Following are some examples. txt[] = "AAAAAAAAAAAAAAAAAB" pat[] = "AAAAB" txt[] = "ABABABCABABABCABABABC" pat[] = "ABABAC" (not a worst case, but a bad case for Naive) The KMP matching algorithm uses degenerating property (pattern having same sub-patterns appearing more than once in the pattern) of the pattern and improves the worst case complexity to O(n). The basic idea behind KMP’s algorithm is: whenever we detect a mismatch (after some matches), we already know some of the characters in the text (since they matched the pattern characters prior to the mismatch). We take advantage of this information to avoid matching the characters that we know will anyway match. The Partial Match Table The key to KMP, of course, is the partial match table. The main obstacle between me and understanding KMP was the fact that I didn’t quite fully grasp what the values in the partial match table really meant. I will now try to explain them in the simplest words possible. Here’s the partial match table for the pattern “abababca”: 1 2 3 char: | a | b | a | b | a | b | c | a | index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 | If I have an eight-character pattern (let’s say “abababca” for the duration of this example), my partial match table will have eight cells. If I’m looking at the eighth and last cell in the table, I’m interested in the entire pattern (“abababca”). If I’m looking at the seventh cell in the table, I’m only interested in the first seven characters in the pattern (“abababc”); the eighth one (“a”) is irrelevant, and can go fall off a building or something. If I’m looking at the sixth cell of the in the table… you get the idea. Notice that I haven’t talked about what each cell means yet, but just what it’s referring to. Now, in order to talk about the meaning, we need to know about proper prefixes and proper suffixes. Proper prefix: All the characters in a string, with one or more cut off the end. “S”, “Sn”, “Sna”, and “Snap” are all the proper prefixes of “Snape”. Proper suffix: All the characters in a string, with one or more cut off the beginning. “agrid”, “grid”, “rid”, “id”, and “d” are all proper suffixes of “Hagrid”. With this in mind, I can now give the one-sentence meaning of the values in the partial match table: The length of the longest proper prefix in the (sub)pattern that matches a proper suffix in the same (sub)pattern. Let’s examine what I mean by that. Say we’re looking in the third cell. As you’ll remember from above, this means we’re only interested in the first three characters (“aba”). In “aba”, there are two proper prefixes (“a” and “ab”) and two proper suffixes (“a” and “ba”). The proper prefix “ab” does not match either of the two proper suffixes. However, the proper prefix “a” matches the proper suffix “a”. Thus, the length of the longest proper prefix that matches a proper suffix, in this case, is 1. Let’s try it for cell four. Here, we’re interested in the first four characters (“abab”). We have three proper prefixes (“a”, “ab”, and “aba”) and three proper suffixes (“b”, “ab”, and “bab”). This time, “ab” is in both, and is two characters long, so cell four gets value 2. Just because it’s an interesting example, let’s also try it for cell five, which concerns “ababa”. We have four proper prefixes (“a”, “ab”, “aba”, and “abab”) and four proper suffixes (“a”, “ba”, “aba”, and “baba”). Now, we have two matches: “a” and “aba” are both proper prefixes and proper suffixes. Since “aba” is longer than “a”, it wins, and cell five gets value 3. Let’s skip ahead to cell seven (the second-to-last cell), which is concerned with the pattern “abababc”. Even without enumerating all the proper prefixes and suffixes, it should be obvious that there aren’t going to be any matches; all the suffixes will end with the letter “c”, and none of the prefixes will. Since there are no matches, cell seven gets 0. Finally, let’s look at cell eight, which is concerned with the entire pattern (“abababca”). Since they both start and end with “a”, we know the value will be at least 1. However, that’s where it ends; at lengths two and up, all the suffixes contain a c, while only the last prefix (“abababc”) does. This seven-character prefix does not match the seven-character suffix (“bababca”), so cell eight gets 1. How to use the Partial Match Table We can use the values in the partial match table to skip ahead (rather than redoing unnecessary old comparisons) when we find partial matches. The formula works like this: If a partial match of length partial_match_length is found and table[partial_match_length] > 1, we may skip ahead partial_match_length - table[partial_match_length - 1] characters. Let’s say we’re matching the pattern “abababca” against the text “bacbababaabcbab”. Here’s our partial match table again for easy reference: 1 2 3 char: | a | b | a | b | a | b | c | a | index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 | The first time we get a partial match is here: 1 2 3 bacbababaabcbab | abababca This is a partial_match_length of 1. The value at table[partial_match_length - 1] (or table[0]) is 0, so we don’t get to skip ahead any. The next partial match we get is here: 1 2 3 bacbababaabcbab ||||| abababca This is a partial_match_length of 5. The value at table[partial_match_length - 1] (or table[4]) is 3. That means we get to skip ahead partial_match_length - table[partial_match_length - 1] (or 5 - table[4] or 5 - 3 or 2) characters: 1 2 3 4 5 // x denotes a skip bacbababaabcbab xx||| abababca This is a partial_match_length of 3. The value at table[partial_match_length - 1] (or table[2]) is 1. That means we get to skip ahead partial_match_length - table[partial_match_length - 1] (or 3 - table[2] or 3 - 1 or 2) characters: 1 2 3 4 5 // x denotes a skip bacbababaabcbab xx| abababca At this point, our pattern is longer than the remaining characters in the text, so we know there’s no match. Code: #include<stdio.h> #include<string.h> #include<stdlib.h> void computeLPSArray(char *pat, int M, int *lps); void KMPSearch(char *pat, char *txt) {     int M = strlen(pat);     int N = strlen(txt);     // create lps[] that will hold the longest prefix suffix values for pattern     int *lps = (int *)malloc(sizeof(int)*M);     int j  = 0;  // index for pat[]     // Preprocess the pattern (calculate lps[] array)     computeLPSArray(pat, M, lps);     int i = 0;  // index for txt[]     while(i < N)     {       if(pat[j] == txt[i])       {         j++;         i++; }       if (j == M)       {         printf("Found pattern at index %d \n", i-j);         j = lps[j-1]; }       // mismatch after j matches       else if(pat[j] != txt[i])       {         // Do not match lps[0..lps[j-1]] characters,         // they will match anyway         if(j != 0)          j = lps[j-1];         else          i = i+1;       }     }     free(lps); // to avoid memory leak } void computeLPSArray(char *pat, int M, int *lps) {     int len = 0;  // lenght of the previous longest prefix suffix     int i;     lps[0] = 0; // lps[0] is always 0     i = 1;     // the loop calculates lps[i] for i = 1 to M-1     while(i < M)     {        if(pat[i] == pat[len])        {          len++;          lps[i] = len;          i++;        }        else // (pat[i] != pat[len])        {          if( len != 0 )          {            // This is tricky. Consider the example AAACAAAA and i = 7.            len = lps[len-1];            // Also, note that we do not increment i here          }          else // if (len == 0)          {            lps[i] = 0;            i++;          }        }     } } int main() {    char *txt = "ABABDABACDABABCABAB";    char *pat = "ABABCABAB";    KMPSearch(pat, txt);    getchar();    return 0; }