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 LinkedBlockingQueueblockingQueue = 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);
}
}
}
Thursday, March 29, 2012
String search on receive a character ( with knuth morris pratt)
Monday, March 26, 2012
Knuth moris pratt in java
package kws.algo.string;
import java.util.Arrays;
/**
* 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 {
public void match(char[] t, char[] p) {
short [] pi = calculatePi(p);
int q = 0; //number of character matched
for(int i = 0; i < t.length; i++) {
while(q > 0 && p[q] != t[i]){
q = pi[q-1];
}
if(p[q] == t[i]) {
q = q + 1;
}
if(q == p.length) {
System.out.println("Pattern found ");
q = pi[q-1];
}
}
}
private short[] calculatePi(char[] p) {
short [] pi = new short[p.length];
pi[0] = 0;
int k = 0;
for (int i = 1; i < p.length; i++) {
while(k > 0 && p[k] != p[i]) {
k = pi[k-1];
}
if(p[k] == p[i]) {
k = k + 1;
}
pi[i] = (short) k;
}
return pi;
}
public static void main(String ... arg) {
KnuthMorrisPratt knuthMorrisPratt = new KnuthMorrisPratt();
knuthMorrisPratt.match("xaababacahsababacagadfasd".toCharArray(), "ababaca".toCharArray());
}
}
Sunday, March 25, 2012
String search on receive a character
package kws.algo.string;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/**
* Created by IntelliJ IDEA.
* User: uchan
* Date: 3/25/12
* Time: 12:56 PM
* To change this template use File | Settings | File Templates.
*/
public class SignalReceiver {
private LinkedList signalReceived = new LinkedList();
private char[] pattern;
public void onReceive(char c){
signalReceived.addLast(c);
int j = 1;
if(signalReceived.size() >= pattern.length) {
for(int i = pattern.length - 1; i > 0; i--){
if(!signalReceived.get(signalReceived.size() - j++).equals(pattern[i])){
return;
}
}
System.out.println("Found the pattern at " + (signalReceived.size() - pattern.length));
}
}
public void setPattern(char[] pattern) {
this.pattern = pattern;
}
public void setReversePattern(char[] pattern) {
setPattern(reverse(pattern));
}
private 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[] args) {
SignalReceiver signalReceiver = new SignalReceiver();
signalReceiver.setPattern("msc".toCharArray());
// signalReceiver.setReversePattern("ccs".toCharArray());
signalReceiver.onReceive('a'); //0
signalReceiver.onReceive('m'); //1 <----
signalReceiver.onReceive('s'); //2 >----
signalReceiver.onReceive('c'); //3
signalReceiver.onReceive('c'); //4
signalReceiver.onReceive('m'); //5 <----
signalReceiver.onReceive('s'); //6
signalReceiver.onReceive('c'); //7
signalReceiver.onReceive('a'); //8
signalReceiver.onReceive('a'); //9
}
}
Subscribe to:
Posts (Atom)