samedi 26 novembre 2016

pattern search in a text by using three methods

I want to write a program for pattern searching in a given text which reads in a text and then one or more patterns and gives for each pattern: if it is found(prints out the position of the first appearance in the text) if not the number of comparison for of the methods: Brute-force, Boyer-Moore Heuristics, and KMP.
But I don't know how to write my main class to get output:

import java.util.HashMap; import java.util.Map;

public class PatternSearch {

/** Returns the lowest index at which substring pattern begins in text (or else -1).*/
 public static int findBrute(char[] text, char[] pattern) { 
 int n = text.length;
 int m = pattern.length;
 for (int i=0; i <= n - m; i++) { // try every starting index within text
 int k = 0; // k is index into pattern
 while (k < m && text[i+k] == pattern[k]) // kth character of pattern matches
 k++;
 if (k == m) // if we reach the end of the pattern,
 return i; // substring text[i..i+m-1] is a match
 } 
    return -1; // search failed
 }

 /** Returns the lowest index at which substring pattern begins in text (or else -1).*/
 public static int findBoyerMoore(char[] text, char[] pattern) {
     int n = text.length;
 int m = pattern.length;
 if (m == 0) return 0; // trivial search for empty string
 Map<Character,Integer> last = new HashMap<>( ); // the 'last' map
 for (int i=0; i < n; i++)
 last.put(text[i], -1); // set -1 as default for all text characters
 for (int k=0; k < m; k++)
 last.put(pattern[k], k); // rightmost occurrence in pattern is last
 // start with the end of the pattern aligned at index m-1 of the text
 int i = m-1; // an index into the text
 int k = m-1; // an index into the pattern
 while (i < n) { 
      if (text[i] == pattern[k]) { // a matching character
 if (k == 0) return i; // entire pattern has been found
 i--; // otherwise, examine previous
 k--; // characters of text/pattern
 } else { 
      i += m - Math.min(k, 1 + last.get(text[i])); // case analysis for jump step
 k = m - 1; // restart at end of pattern
 } 
  } 
 return -1; // pattern was never found
 }


 /** Returns the lowest index at which substring pattern begins in text (or else -1).*/
 public static int findKMP(char[] text, char[] pattern) { 
 int n = text.length;
 int m = pattern.length;
 if (m == 0) return 0; // trivial search for empty string
 int[] fail = computeFailKMP(pattern); // computed by private utility
 int j = 0; // index into text
 int k = 0; // index into pattern
 while (j < n) { 
 if (text[j] == pattern[k]) { // pattern[0..k] matched thus far
 if (k == m - 1) return j - m + 1; // match is complete
 j++; // otherwise, try to extend match
 k++;
 } else if (k > 0)
 k = fail[k-1]; // reuse suffix of P[0..k-1]
 else
 j++;
 } 
 return -1; // reached end without match
 }


 private static int[] computeFailKMP(char[] pattern) { 
 int m = pattern.length;
 int[ ] fail = new int[m]; // by default, all overlaps are zero
 int j = 1;
 int k = 0;
 while (j < m) { // compute fail[j] during this pass, if nonzero
 if (pattern[j] == pattern[k]) { // k + 1 characters match thus far
 fail[j] = k + 1;
 j++;
 k++;
  } else if (k > 0) // k follows a matching prefix
  k = fail[k-1];
  else // no match found starting at j
  j++;
  } 
  return fail;
  }

public static void main(String[] args) {



}

}

Aucun commentaire:

Enregistrer un commentaire