BVB Source Codes

Algorithm-Implementations Show KmpSearch.java Source code

Return Download Algorithm-Implementations: download KmpSearch.java Source code - Download Algorithm-Implementations Source code - Type:.java
  1. package knuth.morris.prat;
  2.  
  3. public class KmpSearch {
  4.  
  5.         /** Failure array **/
  6.         private int[] failure;
  7.  
  8.         /** Constructor **/
  9.  
  10.         public KmpSearch() {
  11.                
  12.         }
  13.  
  14.         public boolean Search(String text, String pat) {
  15.                 /** pre construct failure array for a pattern **/
  16.                 KmpSearch ks = new KmpSearch();
  17.                 ks.failure = new int[pat.length()];
  18.                 ks.fail(pat);
  19.                 /** find match **/
  20.                 int pos = ks.posMatch(text, pat);
  21.                 if (pos == -1)
  22.                         return false;
  23.                 else
  24.                         return true;
  25.         }
  26.  
  27.         /** Test cases can be run by creating a new parameterised object **/
  28.         public KmpSearch(String text, String pat) {
  29.                 /** pre construct failure array for a pattern **/
  30.                 failure = new int[pat.length()];
  31.                 fail(pat);
  32.                 /** find match **/
  33.                 int pos = posMatch(text, pat);
  34.                 if (pos == -1)
  35.                         System.out.println("No match found");
  36.                 else
  37.                         System.out.println("Match found at index " + pos);
  38.         }
  39.  
  40.         /** Failure function for a pattern **/
  41.         private void fail(String pat) {
  42.                 int n = pat.length();
  43.                 failure[0] = -1;
  44.                 for (int j = 1; j < n; j++) {
  45.                         int i = failure[j - 1];
  46.                         while ((pat.charAt(j) != pat.charAt(i + 1)) && i >= 0)
  47.                                 i = failure[i];
  48.                         if (pat.charAt(j) == pat.charAt(i + 1))
  49.                                 failure[j] = i + 1;
  50.                         else
  51.                                 failure[j] = -1;
  52.                 }
  53.         }
  54.  
  55.         /** Function to find match for a pattern **/
  56.         private int posMatch(String text, String pat) {
  57.                 int i = 0, j = 0;
  58.                 int lens = text.length();
  59.                 int lenp = pat.length();
  60.                 while (i < lens && j < lenp) {
  61.                         if (text.charAt(i) == pat.charAt(j)) {
  62.                                 i++;
  63.                                 j++;
  64.                         } else if (j == 0)
  65.                                 i++;
  66.                         else
  67.                                 j = failure[j - 1] + 1;
  68.                 }
  69.                 return ((j == lenp) ? (i - lenp) : -1);
  70.         }
  71. }
  72.  
downloadKmpSearch.java Source code - Download Algorithm-Implementations Source code
Related Source Codes/Software:
raty - 2017-04-22
RDVTabBarController - Highly customizable tabBar and tabBarController fo... 2017-04-22
material-icon-lib - Library containing over 1500 material vector icons... 2017-04-21
httpdiff - Perform the same request against two HTTP servers ... 2017-04-21
jquerytools - The missing UI library for the Web ... 2017-04-21
mcrouter - Mcrouter is a memcached protocol router for scalin... 2017-04-22
dynomite - A generic dynamo implementation for different k-v ... 2017-04-22
kityminder - Baidu brain figure 2017-04-22
llvm - Mirror of official llvm git repository located at ... 2017-04-22
RBBAnimation - Block-based animations made easy, comes with easin... 2017-04-22
ied - 2017-04-29
Nimble - A Matcher Framework for Swift and Objective-C 2017-04-29
MHVideoPhotoGallery - A Photo and Video Gallery 2017-04-29
shoulda-matchers - Collection of testing matchers extracted from Shou... 2017-04-29
Android-SlideExpandableListView - A better ExpandableListView, with animated expanda... 2017-04-29
AppSales-Mobile - App Sales allows iPhone and Mac App Store develope... 2017-04-29
react-templates - Light weight templates for react ... 2017-04-28
afterglow-theme - A minimal dark Theme for Sublime Text 2 and 3 2017-04-28
jwt-go - Golang implementation of JSON Web Tokens (JWT) 2017-04-28
DeerResume - Tool MarkDown online resume, online preview, edit,... 2017-04-28

 Back to top