Array

Knuth Morris Pratt string searching algorithm

Pinterest LinkedIn Tumblr

String searching algorithm helps to search the occurrences of the word within the text string. Write a program to implement Knuth Morris Pratt string searching algorithm.

Algorithm Explanation

Initialize text and word and pass to the utility function.
Iterate all characters from the text and match with the pattern using Knuth-Morris Pratt string searching algorithm.
Return the position of the string.

Source Code

package com.dsacode.DataStructre.array;
 
public class StrMatchKMP {
 
    private String string;
    private String pattern;
    private int[] failure;
    private int matchPoint;
 
    public StrMatchKMP(String string, String pattern) {
        this.string = string;
        this.pattern = pattern;
        failure = new int[pattern.length()];
        computeFailure();
    }
 
    public int getMatchPoint() {
        return matchPoint;
    }
 
    public int match() {
 
        int j = 0;
        if (string.length() == 0)
            return 0;
 
        for (int i = 0; i < string.length(); i++) {
            while (j > 0 && pattern.charAt(j) != string.charAt(i)) {
                j = failure[j - 1];
            }
            if (pattern.charAt(j) == string.charAt(i)) {
                j++;
            }
            if (j == pattern.length()) {
                matchPoint = i - pattern.length() + 1;
                return matchPoint;
            }
        }
        return 0;
    }
 
    private void computeFailure() {
 
        int j = 0;
        for (int i = 1; i < pattern.length(); i++) {
            while (j > 0 && pattern.charAt(j) != pattern.charAt(i)) {
                j = failure[j - 1];
            }
            if (pattern.charAt(j) == pattern.charAt(i)) {
                j++;
            }
            failure[i] = j;
        }
    }
 
    public static void main(String[] args) {
 
        System.out.println("String pattern match using Knuth Morris Pratt Algorithm");
 
        String t = "hfgbcabdabcabd", p = "ab";
        StrMatchKMP bm = new StrMatchKMP(t, p);
 
        System.out.println("String Text:" + t + " Pattern:" + p);
 
        int pos = bm.match();
        if (pos == -1)
            System.out.println("\nNo Match\n");
        else
            System.out.println("Pattern found at position : " + pos);
 
    }
}
    

Output

String pattern match using Knuth Morris Pratt Algorithm
String Text:hfgbcabdabcabd Pattern:ab
Pattern found at position: 5

Write A Comment