Java Program to Implement Bitap Algorithm

This is a Java Program to Implement Bitap Algorithm. The bitap algorithm (also known as the shift-or, shift-and or Baeza-Yates–Gonnet algorithm) is an approximate string matching algorithm. The algorithm tells whether a given text contains a substring which is “approximately equal” to a given pattern, where approximate equality is defined in terms of Levenshtein distance — if the substring and pattern are within a given distance k of each other, then the algorithm considers them equal. The algorithm begins by precomputing a set of bitmasks containing one bit for each element of the pattern. Then it is able to do most of the work with bitwise operations, which are extremely fast.

Here is the source code of the Java Program to Implement Bitap Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

```
/**
```

 ** Java Program to implement Bitap Algorithm

```
 **/
```
```
 
```
```
import java.io.BufferedReader;
```
```
import java.io.InputStreamReader;
```
```
import java.io.IOException;
```
```
 
```
```
/** Class Bitap **/
```
```
public class Bitap
```
```
{
```
```
    /** function findPattern **/
```

    public void findPattern(String t, String p)

```
    {
```
```
        char[] text = t.toCharArray();
```

        char[] pattern = p.toCharArray();

        int pos = bitap_search(text, pattern);

```
        if (pos == -1)
```

            System.out.println("\nNo Match\n");

```
        else
```

            System.out.println("\nPattern found at position : "+ pos);

```
    }
```
```
    /** Bitap search **/
```

    private int bitap_search(char[] text, char[] pattern)

```
    {
```
```
        int m = pattern.length;        
```

        long pattern_mask[] = new long[Character.MAX_VALUE + 1];

        /** Initialize the bit array R **/

```
        long R = ~1;        
```
```
        if (m == 0)
```
```
            return -1;
```
```
        if (m > 63)
```
```
        {
```

            System.out.println("Pattern is too long!");

```
            return -1;
```
```
        }
```

        /** Initialize the pattern bitmasks **/

        for (int i = 0; i <= Character.MAX_VALUE; ++i)

```
            pattern_mask[i] = ~0;
```
```
        for (int i = 0; i < m; ++i)
```

               pattern_mask[pattern[i]] &= ~(1L << i);

        for (int i = 0; i < text.length; ++i)

```
        {
```

               /** Update the bit array **/

```
            R |= pattern_mask[text[i]];
```
```
            R <<= 1;     
```
```
            if ((R & (1L << m)) == 0)
```
```
                 return i - m + 1;
```
```
        }
```
```
        return -1;
```
```
    }
```
```
    /** Main Function **/
```

    public static void main(String[] args) throws IOException

```
    {    
```

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        System.out.println("Bitap Algorithm Test\n");

        System.out.println("\nEnter Text\n");

```
        String text = br.readLine();
```

        System.out.println("\nEnter Pattern\n");

```
        String pattern = br.readLine();
```
```
        Bitap b = new Bitap(); 
```

        b.findPattern(text, pattern);

```
    }
```
```
}
```

Bitap Algorithm Test
 
 
Enter Text
 
bitapalgorithmtest
 
Enter Pattern
 
algorithm
 
Pattern found at position : 5

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

If you wish to look at all Java Programming examples, go to Java Programs.

If you find any mistake above, kindly email to [email protected]

« Prev - Java Program to Implement Horner Algorithm

» Next - Java Program to Implement Pollard Rho Algorithm

Related Posts:

Recommended Articles: