Java Program to Implement Zhu–Takaoka String Matching Algorithm

Zhu-Takaoka String Matching Algorithm is a Variant of Boyer Moore Algorithm for Pattern Matching in a String. There is a slight change in the concept of Bad Maps in this algorithm. The concept of Good Suffixes remains as same as that of Boyer Moore’s but instead of using a single character for Bad Shifts, now in this algorithm, we will be performing two shifts.

Hence, this algorithm provides a little speed over the Boyer’s one. Both Good suffixes and Two character Bad shifts can be used together in the code to give an extra edge in the performance of the Algorithm. We are discussing the idea of how to change the calculation of Bad Character Shifts for this algorithm and the idea of Good suffixes can be derived from Boyer’s algorithm.

Working of Algorithms:

At first, this algorithm starts the same as that of Boyer’s one starts i.e. comparing the pattern to the string from Right to Left. Hence, each character of the pattern is compared to that of string from Right to Left. So the starting index of the comparison should be the length of the pattern.

String :     ABCDEFGH

Pattern:    BCD

So the comparison should begin at the index of ‘C’ in string i.e. 2 (0-based indexing is used). So comparison starts at index = Length of Pattern – 1. If a match is found then the index is decremented till the matches are found. Once the match is not found then it’s time to make shifts for Bad Characters.

String :     ABCDEFGH

Pattern:    BCC

a) At index 2 String has Char ‘C’ and since Pattern[2]==’C’ so character match is found. So we are now going to check for previous indexes i.e. 1, 0. So at string[1] (which is equal to ‘B”), Pattern[1]!=’B’ So the match is not found and is the time to shift the characters.

Computing table for Bad Character Shifts (named ZTBC Table): This stage is a preprocessing stage i.e. should be done before starting the comparisons. Bad Character tables is a Hash Map which has all alphabets of Pattern as the keys and the value represents the number of shift the pattern should be given so that either:

• The mismatch becomes a match.
• The pattern passed that mismatched character of the string.

So in Zhu-Takaoka Algorithm, we are maintaining a 2-D array that can give the number of shifts based on the first two characters of the string from where the comparison had started. Hence, increasing the number of shifts and decreasing the number of comparisons which results in more increased performance.

Procedure: Logic building. The idea for computing the table is as depicted below: 

The table is made using a 2D Array where all the columns and rows are named by the character of the Patterns. The table is initialized with the length of the pattern since if the pair of char is not found in the pattern then the only way is to pass the whole pattern through pass the mismatched character.

If pattern is  = "ABCD"

The ZTBC =  A  B  C  D  E...

                 A  4  4  4  4  4 

                 B  4  4  4  4  4

                 C  4  4  4  4  4

                 D  4  4  4  4  4

                 E.....

Now if out of the two char if the second one is the starting character of the pattern then shifting the whole pattern is not the right idea we should make a match of the second char with the first one of the pattern. So we should shift the pattern by Len-1.

so For all i in size of array 

ZTBC[i][pattern[0]] = len-1.

so ZTBC now looks like :

ZTBC =         A  B  C  D  E....

                A   3  4  4  4  4

                B   3  4  4  4  4

                C   3  4  4  4  4

                D   3  4  4  4  4

                E.....

Now if both characters are found consecutively in the pattern then we should shift the pattern only that much so that the pair of chars in string and pattern matches so.

for all i in array.size

ZTBC[pattern[i-1]][pattern[i]] = len-i-1 ; //This is the amount of shifts if two matching pair is found.

So finally ZTBC looks like

ZTBC =         A  B  C  D  E ......

                A   3  2  4  4  4

                B   3  4  1  4  4

                C   3  4  4  4  4

                D   3  4  4  4  4

                E.......

Illustration: 

Hence, suppose a string and pattern is given as below:

String S  = "ABCABCDE"
Pattern P = "ABCD"

It is descriptively shown with the help of visual arts below as follows:

So considering 0-Based indexing, we will begin at index 3

so s[3]!=P[3]  // p[3]=='D' and S[3]=='A'

Hence, a mismatch occurs, and we will shift the array by 

ZTBC[C][A] since last two consecutive char is CA in string. 

So now we will shift the pattern by 3 

Since ZTBC[C][A] == 3, and now we are at index 6 ( 3+3 )

And now we should again start a comparison of the string and pattern as in step 1, and then we would found a match of pattern in the string so print it. We found one occurrence. Now since continuing further, we should now shift by the last two char i.e. CD in String since they are only at the previous index. Hence, we should shift our pattern by 1 and continue the same process. Also, we can include the idea of Good Suffixes in this program to find the max number of shifts necessary and hence make our code’s performance better. The idea of Good Suffixes is the same as that in Boyer’s one. Hence, presenting a general formula for the above shifting idea we get If a mismatch occurs at Char of String. Say

Say S[i+m-k]!=P[m-k] //m is the size of pattern and j is the index of the start of matching .

Then the number of the shift should be given as:

ZTBC[S[i+m-2]][S[i+m-1]] // two consecutive char at the index where comparisons starts.

Example:

Pattern Found at 4
Pattern Found at 9

Note:

• Runtime complexity is found to be O(stringlen*patternlen) For searching one and O(patterlen + (26*26)).
• Space Complexity is found to be O(26×26) which is constant nearly for large test cases.