Thursday, March 29, 2012

String search on receive a character ( with knuth morris pratt)


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.concurrent.LinkedBlockingQueue;

/**
* Created by IntelliJ IDEA.
* User: uchan
* Date: 3/27/12
* Time: 9:10 AM
* To change this template use File | Settings | File Templates.
*/
public class KnuthMorrisPratt {

private boolean running = true;
private LinkedBlockingQueue blockingQueue = new LinkedBlockingQueue();

/**
* Initialize the character processing thread. Pass the thread need to be match
* @param pattern
*/
public void init(final char[] pattern){
Thread thread = new Thread(){ //Below thread will listen for any character received
public void run(){
try {
KnuthMorrisPratt.this.match(pattern);
} catch (Exception e) {
System.out.println("Unexpected error occurred " + e.getMessage());
}
}
};
thread.start();
}

/**
* This will match for any received characters for the given pattern. Knuth morris pratt algorithm is used for String matching.
* @param pattern
* @throws InterruptedException
*/
public void match(char[] pattern) throws InterruptedException {
short [] pi = calculatePi(pattern);
int q = 0; //number of character matched
int i = 0;
while (running) {
char receivedCharacter = blockingQueue.take();
while(q > 0 && pattern[q] != receivedCharacter){
q = pi[q-1];
}
if(pattern[q] == receivedCharacter) {
q = q + 1;
}
if(q == pattern.length) {
System.out.println("Pattern found at [" + (i - pattern.length + 1) + "]");
q = pi[q-1];
}
i++;
}
}


/**
* Generate pi array for a given pattern
* @param pattern
* @return pi
*/
private short[] calculatePi(char[] pattern) {
short [] pi = new short[pattern.length];
pi[0] = 0;
int k = 0;
for (int i = 1; i < pattern.length; i++) {
while(k > 0 && pattern[k] != pattern[i]) {
k = pi[k-1];
}
if(pattern[k] == pattern[i]) {
k = k + 1;
}
pi[i] = (short) k;
}
return pi;
}

/**
* Add character to process for the given pattern
* @param character
*/
public void addCharacterToProcess(Character character){
blockingQueue.add(character);
}

/**
* Convert a text sequence to reverse
* @param pattern
* @return
*/
private static char[] reverse(char[] pattern) {
char[] reversePattern = new char[pattern.length];
for (int i = 0; i < pattern.length; i++) {
reversePattern[pattern.length - 1- i] = pattern[i];
}
return reversePattern;
}

public static void main(String ... arg) throws IOException {

if(arg.length != 1 && arg.length != 2) {
System.out.print("Pass the pattern as an argument");
return;
}

char[] pattern = arg[0].toCharArray();

if(arg.length == 2) {
String reverse = arg[1];
if(reverse.equals("reverse=true")) {
pattern = reverse(pattern);
}
}

System.out.println("Matching pattern [" + new String(pattern) +"]");
System.out.println("Type a text and press enter");

KnuthMorrisPratt knuthMorrisPratt = new KnuthMorrisPratt();
knuthMorrisPratt.init(pattern);

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

while (true) {
char c = (char) reader.read();
knuthMorrisPratt.addCharacterToProcess(c);
}

}
}

No comments:

Post a Comment