Boyer Moore algorithm

/**
 ** Java Program to implement Boyer Moore Algorithm
 **/
package AdvancedAlgo;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

/** Class BoyerMoore **/
public class BoyerMoore
{
    /** function findPattern **/
    public void findPattern(String t, String p)
    {
        char[] text = t.toCharArray();
        char[] pattern = p.toCharArray();
        int pos = indexOf(text, pattern);
        if (pos == -1)
            System.out.println("\nNo Match\n");
        else
            System.out.println("Pattern found at position : "+ pos);
    }
    /** Function to calculate index of pattern substring **/
    public int indexOf(char[] text, char[] pattern)
    {
        if (pattern.length == 0)
            return 0;
        int charTable[] = makeCharTable(pattern);
        int offsetTable[] = makeOffsetTable(pattern);
        for (int i = pattern.length - 1, j; i < text.length;)
        {
            for (j = pattern.length - 1; pattern[j] == text[i]; --i, --j)
                     if (j == 0)
                    return i;

              // i += pattern.length - j; // For naive method
              i += Math.max(offsetTable[pattern.length - 1 - j], charTable[text[i]]);
        }
        return -1;
      }
      /** Makes the jump table based on the mismatched character information **/
      private int[] makeCharTable(char[] pattern)
      {
        final int ALPHABET_SIZE = 256;
        int[] table = new int[ALPHABET_SIZE];
        for (int i = 0; i < table.length; ++i)
               table[i] = pattern.length;
        for (int i = 0; i < pattern.length - 1; ++i)
               table[pattern[i]] = pattern.length - 1 - i;
        return table;
      }
      /** Makes the jump table based on the scan offset which mismatch occurs. **/
      private static int[] makeOffsetTable(char[] pattern)
      {
        int[] table = new int[pattern.length];
        int lastPrefixPosition = pattern.length;
        for (int i = pattern.length - 1; i >= 0; --i)
        {
            if (isPrefix(pattern, i + 1))
                   lastPrefixPosition = i + 1;
              table[pattern.length - 1 - i] = lastPrefixPosition - i + pattern.length - 1;
        }
        for (int i = 0; i < pattern.length - 1; ++i)
        {
              int slen = suffixLength(pattern, i);
              table[slen] = pattern.length - 1 - i + slen;
        }
        return table;
    }
    /** function to check if needle[p:end] a prefix of pattern **/
    private static boolean isPrefix(char[] pattern, int p)
    {
        for (int i = p, j = 0; i < pattern.length; ++i, ++j)
            if (pattern[i] != pattern[j])
                  return false;
        return true;
    }
    /** function to returns the maximum length of the substring ends at p and is a suffix **/
    private static int suffixLength(char[] pattern, int p)
    {
        int len = 0;
        for (int i = p, j = pattern.length - 1; i >= 0 && pattern[i] == pattern[j]; --i, --j)
               len += 1;
        return len;
    }
    /** Main Function **/
    public static void main(String[] args) throws IOException
    {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Boyer Moore Algorithm Test\n");
        System.out.println("\nEnter Text\n");
        String text = br.readLine();
        System.out.println("\nEnter Pattern\n");
        String pattern = br.readLine();
        BoyerMoore bm = new BoyerMoore();
        bm.findPattern(text, pattern);    
    }
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Input/Output:

Boyer Moore Algorithm Test


Enter Text

hello how are you

Enter Pattern

are
Pattern found at position : 10

Miller Rabin Primality Testing

Primality Testing:

/**Java Program to Implement Miller Rabin Primality Test Algorithm**/

package AdvancedAlgo;
import java.util.Scanner;
import java.util.Random;
import java.math.BigInteger;

/** Class MillerRabin **/
public class MillerRabin
{
    /** Function to check if prime or not **/
    public boolean isPrime(long n, int iteration)
    {
       /** base case **/
       if (n == 0 || n == 1)
            return false;
        /** base case - 2 is prime **/
        if (n == 2)
           return true;
       /** an even number other than 2 is composite **/
       if (n % 2 == 0)
           return false;
       long s = n - 1;
       while (s % 2 == 0)
           s /= 2;
       Random rand = new Random();
       for (int i = 0; i < iteration; i++)
       {
           long r = Math.abs(rand.nextLong());          
           long a = r % (n - 1) + 1, temp = s;
           long mod = modPow(a, temp, n);
           while (temp != n - 1 && mod != 1 && mod != n - 1)
           {
               mod = mulMod(mod, mod, n);
               temp *= 2;
           }
           if (mod != n - 1 && temp % 2 == 0)
                return false;
        }
        return true;      
    }

    /** Function to calculate (a ^ b) % c **/
    public long modPow(long a, long b, long c)
    {
       long res = 1;
       for (int i = 0; i < b; i++)
       {
           res *= a;
           res %= c;
       }
       return res % c;
    }

   /** Function to calculate (a * b) % c **/
   public long mulMod(long a, long b, long mod)
   {
       return BigInteger.valueOf(a).multiply(BigInteger.valueOf(b)).mod(BigInteger.valueOf(mod)).longValue();
   }

   /** Main function **/
   public static void main (String[] args)
   {
       Scanner scan = new Scanner(System.in);
       System.out.println("Miller Rabin Primality Algorithm Test\n");

       /** Make an object of MillerRabin class **/
       MillerRabin mr = new MillerRabin();

      /** Accept number **/
       System.out.println("Enter number\n");
       long num = scan.nextLong();

       /** Accept number of iterations **/
       System.out.println("\nEnter number of iterations");

       int k = scan.nextInt();
       /** check if prime **/
       boolean prime = mr.isPrime(num, k);
       if (prime)
            System.out.println("\n"+ num +" is prime");
       else
            System.out.println("\n"+ num +" is composite");
    }
}


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Input/Output:

Miller Rabin Primality Algorithm Test

Enter number

65537

Enter number of iterations
100

65537 is prime

Rabin Karp pattern Matching Algorithm

/**
 ** Java Program to Implement Rabin Karp Pattern Matching Algorithm
 **/

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Random;
import java.math.BigInteger;

public class RabinKarp
{
    private String pat; /** String Pattern **/
    private long patHash; /** pattern hash value **/
    private int M;   /** pattern length **/
    private long Q; /** Large prime **/
    private int R; /** radix **/
    private long RM; /** R^(M-1) % Q **/
    private int KeyCount; /** key operation counter **/

    public RabinKarp(String txt, String pat) /** Constructor **/
    {
        this.pat = pat;
        R = 256;
        M = pat.length();
        Q = longRandomPrime();
        KeyCount = 0;

        /** precompute R^(M-1) % Q for use in removing leading digit **/
        RM = 1;
        for (int i = 1; i <= M-1; i++)
           RM = (R * RM) % Q;
        patHash = hash(pat, M);
        int pos = search(txt);
        if (pos == -1)
            System.out.println("\nNo Match\n");
        else {
        System.out.println("Pattern found at position : "+ pos);
        System.out.println("\nNo of comparisons : " + KeyCount );
        }
    }

    /** Compute hash **/
    private long hash(String key, int M)
    {
        long h = 0;
        for (int j = 0; j < M; j++)
            h = (R * h + key.charAt(j)) % Q;
        return h;
    }

    /** Funtion check **/
    private boolean check(String txt, int i)
    {
        for (int j = 0; j < M; j++){
        KeyCount++;
        if (pat.charAt(j) != txt.charAt(i + j))
                return false;
        }
        return true;
    }

    /** Funtion to check for exact match**/
    private int search(String txt)
    {
        int N = txt.length();
        if (N < M) return N;
        long txtHash = hash(txt, M);

        if ((patHash == txtHash) && check(txt, 0)) /** check for match at start **/
            return 0;

        /** check for hash match. if hash match then check for exact match**/
        for (int i = M; i < N; i++)
        {
            // Remove leading digit, add trailing digit, check for match.
            txtHash = (txtHash + Q - RM * txt.charAt(i - M) % Q) % Q;
            txtHash = (txtHash * R + txt.charAt(i)) % Q;
            // match
            int offset = i - M + 1;
            if ((patHash == txtHash) && check(txt, offset))
                return offset;
        }

        return -1; /** no match **/
    }

    /** generate a random 31 bit prime **/
    private static long longRandomPrime()
    {
        BigInteger prime = BigInteger.probablePrime(31, new Random());
        return prime.longValue();
    }

    /** Main Function **/
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Rabin Karp Algorithm Test\n");
        System.out.println("\nEnter Text\n");
        String text = br.readLine();
        System.out.println("\nEnter Pattern\n");
        String pattern = br.readLine();
        System.out.println("\nResults : \n");
        RabinKarp rk = new RabinKarp(text, pattern);
    }
}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Input/Output:

Rabin Karp Algorithm Test

Enter Text

Hello How are you

Enter Pattern

are

Results : 

Pattern found at position : 10

No of comparisons : 3

(Please note: WTF   #$@%!^^ Just 3)

Knuth Morris Pratt Algorithm for Pattern Matching

/**
 ** Java Program to implement Knuth Morris Pratt Algorithm
 **/

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class KnuthMorrisPratt
{
    private int[] failure; /** Failure array **/
    private int KeyCount; /** key operation counter **/

    public KnuthMorrisPratt(String text, String pat) /** Constructor **/
    {
        KeyCount = 0;
        failure = new int[pat.length()]; /** pre construct failure array for a pattern **/
        fail(pat);
        int pos = posMatch(text, pat); /** find match **/
        if (pos == -1)
            System.out.println("\nNo match found");
        else {
        System.out.println("\nMatch found at index "+ pos);
        System.out.println("\nNo of comparisons : " + KeyCount );
        }
    }

    /** Failure function for a pattern **/
    private void fail(String pat)
    {
        int n = pat.length();
        failure[0] = -1;
        for (int j = 1; j < n; j++)
        {
            int i = failure[j - 1];
            //KeyCount++;
            while ((pat.charAt(j) != pat.charAt(i + 1)) && i >= 0){
            i = failure[i];
            //KeyCount++;
            }


            if (pat.charAt(j) == pat.charAt(i + 1))
                failure[j] = i + 1;
            else
                failure[j] = -1;
        }
    }

    /** Function to find match for a pattern **/
    private int posMatch(String text, String pat)
    {
        int i = 0, j = 0;
        int lens = text.length();
        int lenp = pat.length();
        while (i < lens && j < lenp)
        {
        KeyCount++;
            if (text.charAt(i) == pat.charAt(j))
            {
                i++;
                j++;
            }
            else if (j == 0)
                i++;
            else
                j = failure[j - 1] + 1;
        }
        return ((j == lenp) ? (i - lenp) : -1);
    }

    /** Main Function **/
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Knuth Morris Pratt Test\n");
        System.out.println("\nEnter Text\n");
        String text = br.readLine();
        System.out.println("\nEnter Pattern\n");
        String pattern = br.readLine();
        KnuthMorrisPratt kmp = new KnuthMorrisPratt(text, pattern);
    }
}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Input-Output:

Knuth Morris Pratt Test

Enter Text

hello how are you

Enter Pattern

are

Match found at index 10

No of comparisons : 13

Pattern Matching using Deterministic Finite Automaton

Pattern Matching using DFA in Java:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
package AdvancedAlgo;
import java.util.Scanner;
public class DFA {
public static final int NO_OF_CHARS = 256;
public static int getNextState(char[] pat, int M, int state, int x) {
/* If the character c is same as next character in pattern,then simply increment state*/
if (state < M && x == pat[state])
return state + 1;
int ns, i;

/* ns stores the result which is next state ns finally contains the longest prefix which is
* also suffix in "pat[0..state-1]c". Start from the largest possible value and stop when
* you find a prefix which is also suffix
**/
for (ns = state; ns > 0; ns--) {
if (pat[ns - 1] == x) {
for (i = 0; i < ns - 1; i++) {
if (pat[i] != pat[state - ns + 1 + i])
break;
}
if (i == ns - 1)
return ns;
}
}
return 0;
}

/*
* This function builds the TF table which represents Finite Automata for a
* given pattern
*/
public static void computeTF(char[] pat, int M, int[][] TF) {
int state, x;

for (state = 0; state <= M; ++state)
for (x = 0; x < NO_OF_CHARS; ++x)
TF[state][x] = getNextState(pat, M, state, x);
}

/*
* Prints all occurrences of pat in txt
*/
public static void search(char[] pat, char[] txt) {
int M = pat.length;
int N = txt.length;
int[][] TF = new int[M + 1][NO_OF_CHARS];
computeTF(pat, M, TF);

// Process txt over FA.
int i, state = 0;
for (i = 0; i < N; i++) {
state = TF[state][txt[i]];
if (state == M) {
System.out.print(" \npattern found at position: " + (i - M + 1));
}
}
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter the main string: ");
String textStr = sc.nextLine();
System.out.println("Enter the pattern string: ");
String pattern = sc.nextLine();

search(pattern.toCharArray(), textStr.toCharArray());
sc.close();
}
}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Input/Output:

Enter the main string:
abcdefghijklmnopqrstuvwxy
Enter the pattern string:
xy

pattern found at position: 23

Bellman Ford Algorithm

Bellman Ford Algorithm
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

package AdvancedAlgo;
import java.io.*;
import java.util.Scanner;

public class BellmanFord
{
    private int distances[ ];
    private int numberofvertices;
    public static final int MAX_VALUE = 999;
    private int source;
    private int adjacencymatrix[ ][ ];

    public BellmanFord( ) throws IOException{
    Scanner scanner = new Scanner(System.in);

        System.out.println("Enter the number of vertices");
        numberofvertices = scanner.nextInt();
        distances = new int[numberofvertices + 1];

        adjacencymatrix = new int[numberofvertices + 1][numberofvertices + 1];
        System.out.println("Enter the adjacency matrix");
        for (int sourcenode = 1; sourcenode <= numberofvertices; sourcenode++)
                    for (int destinationnode = 1; destinationnode <= numberofvertices; destinationnode++)
               {
                adjacencymatrix[sourcenode][destinationnode] = scanner.nextInt();
          if (sourcenode == destinationnode)
                {
                    adjacencymatrix[sourcenode][destinationnode] = 0;
                    continue;
                }
                if (adjacencymatrix[sourcenode][destinationnode] == 0)
                adjacencymatrix[sourcenode][destinationnode] = MAX_VALUE;
                }

        System.out.println("Enter the source vertex");
        source = scanner.nextInt();
        BellmanFordEvaluation( );
        scanner.close();
    }

    public void BellmanFordEvaluation( ){
        for (int node = 1; node <= numberofvertices; node++)
                    distances[node] = MAX_VALUE;
        distances[source] = 0;
        for (int node = 1; node <= numberofvertices - 1; node++)
                    for (int sourcenode = 1; sourcenode <= numberofvertices; sourcenode++)
                        for (int destinationnode = 1; destinationnode <= numberofvertices; destinationnode++)
                            if (adjacencymatrix[sourcenode][destinationnode] != MAX_VALUE)
                                if (distances[destinationnode] > distances[sourcenode] + adjacencymatrix[sourcenode][destinationnode])
                            distances[destinationnode] = distances[sourcenode]  + adjacencymatrix[sourcenode][destinationnode];
        for (int sourcenode = 1; sourcenode <= numberofvertices; sourcenode++)
                    for (int destinationnode = 1; destinationnode <= numberofvertices; destinationnode++)
                        if (adjacencymatrix[sourcenode][destinationnode] != MAX_VALUE)
                            if (distances[destinationnode] > distances[sourcenode] + adjacencymatrix[sourcenode][destinationnode]){
                            System.out.println("The Graph contains negative edge cycle");
                            return;
                            }

        for (int vertex = 1; vertex <= numberofvertices; vertex++)
                    System.out.println("distance of source  " + source + " to " + vertex + " is " + distances[vertex]);
    }

    public static void main(String... arg) throws IOException {
        BellmanFord bellmanford = new BellmanFord( );
    }
}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Input/Output:

Enter the number of vertices
5
Enter the adjacency matrix
0 6 999 999 7
999 0 5 -4 8
999 -2 0 999 999
2 999 7 0 999
0 999 -3 9 0
Enter the source vertex
1
distance of source  1 to 1 is 0
distance of source  1 to 2 is 2
distance of source  1 to 3 is 4
distance of source  1 to 4 is -2
distance of source  1 to 5 is 7

Naive String Matching

This Algorithm/Code in Java performs naive string matching:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

package AdvancedAlgo;
import java.util.Scanner;

public class NaiveMethod {
private final int BASE;
private int[ ] occurrence;
private String pattern;
public int KeyCount; /** key operation counter **/

public NaiveMethod(String pattern) {
this.BASE = 256;
this.pattern = pattern;
KeyCount = 0;
occurrence = new int[BASE];

for (int c = 0; c < BASE; c++)
occurrence[c] = -1;
for (int j = 0; j < pattern.length(); j++)
occurrence[pattern.charAt(j)] = j;
}

public int search(String text) {
int n = text.length();
int m = pattern.length();
int skip;
for (int i = 0; i <= n - m; i += skip) {
skip = 0;
for (int j = m - 1; j >= 0; j--) {
KeyCount++;
if (pattern.charAt(j) != text.charAt(i + j)) {
skip = Math.max(1, j - occurrence[text.charAt(i + j)]);
break;
}
}
if (skip == 0)
return i;
}
return n;
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter the main string: ");
String text = sc.nextLine();
System.out.print("Enter the string to be searched: ");
String pattern = sc.nextLine();
NaiveMethod nsm = new NaiveMethod(pattern);
int first_occur_position = nsm.search(text);
System.out.println("The text '" + pattern + "' is first found after the " + first_occur_position
+ " position.");
System.out.println("\nNo of comparisons : " + nsm.KeyCount );
sc.close();
}
}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


Input / Output:

Enter the main string: Hello How are You
Enter the string to be searched: are
The text 'are' is first found after the 10 position.

No of comparisons : 7