Saturday 13 September 2014

String Matching algorithm ||finite automata||kmp algorithm|| application in java

import java.awt.Dimension;
import java.awt.FlowLayout;
import java.awt.Font;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.Random;

import javax.swing.*;


public class stringApp extends JFrame {


JPanel panelTop,panelMid,panelLower,panelButton;
JTextField text,noChar,lenText,pattern;
JButton generate,reset,compute,showPre;
JRadioButton b1,b2,b3,b4,b5;
JTextArea result=new JTextArea();;
JScrollPane scrolltxt = new JScrollPane(result);
static String strText="",strPattern="";
static String index="";
static int gobalNochar,gobalLen,gobalPlen,iteration,comparisons;
static int table[][];
static int prefixTable[];
public stringApp()
{
setTitle("Pattern Matching App © Shaharyar");
setSize(600, 600);
setResizable(false);
setLocation(300,50);
setVisible(true);
setLayout(null);
setDefaultCloseOperation(EXIT_ON_CLOSE);
addComponent();

}
public void addComponent()
{

panelTop=new JPanel();
panelTop.setLayout(new FlowLayout());
panelTop.setBounds(10, 10, 580, 70);
//input string
text=new JTextField();
text.setPreferredSize(new Dimension(580,30));
Font font = new Font("SansSerif", Font.BOLD, 25);
text.setFont(font);
//Top panel
JLabel lbl1=new JLabel("No. of Characters:");
lbl1.setPreferredSize(new Dimension(110,30));
JLabel lbl12=new JLabel("Lenght of the Text:");
lbl1.setPreferredSize(new Dimension(110,30));
noChar=new JTextField();
noChar.setPreferredSize(new Dimension(50,30));
lenText=new JTextField();
lenText.setPreferredSize(new Dimension(50,30));
generate=new JButton("Genrate Random Text");
generate.setPreferredSize(new Dimension(180,30));
generate.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent e){

random();

}
});
panelTop.add(text);
panelTop.add(lbl1);
panelTop.add(noChar);
panelTop.add(lbl12);
panelTop.add(lenText);
panelTop.add(generate);
//Mid panel
panelMid=new JPanel();
panelMid.setLayout(new FlowLayout());
panelMid.setBounds(10, 100, 580, 50);
JLabel lbl2=new JLabel("Pattern:");
lbl2.setPreferredSize(new Dimension(50,30));
pattern=new JTextField();
pattern.setPreferredSize(new Dimension(400,30));
panelMid.add(lbl2);
panelMid.add(pattern);
// radio button panel
panelLower=new JPanel();
panelLower.setLayout(new FlowLayout());
panelLower.setBounds(10, 150, 580, 70);
b1=new JRadioButton("Brute Force"  , true);
b2=new JRadioButton("Finte Automata"  , false);
b3=new JRadioButton("KMP Algorithm"  , false);
b4=new JRadioButton("Robin-Karp"  , false);
b5=new JRadioButton("Boyer Moore and Horspool"  , false);
ButtonGroup bgroup = new ButtonGroup();
bgroup.add(b1);
bgroup.add(b2);
bgroup.add(b3);
bgroup.add(b4);
bgroup.add(b5);
panelLower.add(b1);
panelLower.add(b2);
panelLower.add(b3);
panelLower.add(b4);
panelLower.add(b5);
//button panel
panelButton=new JPanel();
panelButton.setLayout(new FlowLayout(FlowLayout.CENTER,40,0));
panelButton.setBounds(10, 220, 580, 50);
reset=new JButton("Reset");
reset.setPreferredSize(new Dimension(80,30));
compute=new JButton("Compute");
compute.setPreferredSize(new Dimension(100,30));
showPre=new JButton("Show Preprocessing of Text");
showPre.setPreferredSize(new Dimension(200,30));
panelButton.add(reset);
panelButton.add(compute);
panelButton.add(showPre);
reset.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent e){
strText="";strPattern="";index="";
gobalNochar=0;gobalLen=0;gobalPlen=0;iteration=0;comparisons=0;
text.setText("");noChar.setText("");lenText.setText("");pattern.setText("");

}
});
compute.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent e){
initialize();
if(b1.isSelected())
{
bruteForce();
display();
}
if(b2.isSelected())
{
table=new int[gobalPlen+1][gobalNochar];
computeState();
match();
display();
displayStateTable();

}
if(b3.isSelected())
{
prefixTable=new int[gobalPlen];
buildprefixTable();

displayprefixTable();
}
if(b4.isSelected())
{

}


}
});

//output text area
result.setFont(font);
scrolltxt.setBounds(10, 270, 570, 280);
result.setEditable(false);
//
add(panelTop);
add(panelMid);
add(panelLower);
add(panelButton);
add(scrolltxt);
    validate();

}
public static void main(String args[])
{
stringApp obj=new stringApp();

}
//random input
public void random()
{
int nchar,len;
String str1,str2,str3="";
str1=noChar.getText();
nchar=Integer.parseInt(str1);
str2=lenText.getText();
len=Integer.parseInt(str2);
Random rand =new Random();
for(int i=0;i<len;i++)
{
int temp=rand.nextInt(nchar);
char tempchar=(char) (65+temp);
str3=str3+tempchar;
}
//text.setText(Integer.toString(len));
text.setText(str3);
}
//
public void initialize()
{
strText=text.getText();
gobalNochar=Integer.parseInt(noChar.getText());
gobalLen=strText.length();
strPattern=pattern.getText();
gobalPlen=strPattern.length();
iteration=0;comparisons=0;
index="";

}
//brute Force
public void bruteForce()
{
for(int i=0;i<=gobalLen-gobalPlen;i++)
{
int j=0;
while(j<gobalPlen&&strText.charAt(i+j)==strPattern.charAt(j))
{
j++;
comparisons++;
}
if(j==gobalPlen)
{
index=index+"-"+Integer.toString(i);

}
iteration++;
}
comparisons=comparisons+iteration;
}
//finite Automation
static void computeState()
{
for(int i=0;i<=gobalPlen;i++)
{
for(int j=0;j<gobalNochar;j++)
{
table[i][j]=nextState(i,j);
}
}

}
//
static int nextState(int state,int chr)
{
char tempChar=(char)(chr+65);
if(state<gobalPlen&& tempChar==strPattern.charAt(state))
{
return state+1;
}
int c=0;



while(c<state)
{
String str1=strPattern.substring(0, state-c);
String str2=strPattern.substring(0+1+c, state);
str2=str2+tempChar;
if(str1.equals(str2))
{
return state-c;
}else
{
c++;
}

}


return 0;
}
//match
static void match()
{
int i,state=0;
for(i=0;i<gobalLen;i++)
{
int temp=((int)strText.charAt(i))-65;
state=table[state][temp];
if(state==gobalPlen)
{
index=index+"-"+Integer.toString(i-gobalPlen+1);
}
iteration++;
}
comparisons=iteration;
}
// Display state Table
 public void displayStateTable()
{
 result.append("\t\tSTATE TABLE\n");
for(int j=0;j<gobalNochar;j++)
{
result.append("\t"+(char)(j+65));
}
for(int i=0;i<=gobalPlen;i++)
{
result.append("\n"+Integer.toString(i));
for(int j=0;j<gobalNochar;j++)
{
result.append("\t"+Integer.toString(table[i][j]));

}
}

}
 //KMP
 static void buildprefixTable()
 {
 int i=1,j=0;
 prefixTable[0]=0;
 while(i<gobalPlen)
 {
 if(strPattern.charAt(i)==strPattern.charAt(j))
 {
 prefixTable[i]=j+1;
 i++;
 j++;
 }else if(j>0)
 {
 j=prefixTable[j-1];
 }else
 {
 prefixTable[i]=0;
 i++;
 }
 }
 }
 //Display prefix table
 void displayprefixTable()
 {
 //result.setText("");
 for(int i=0;i<gobalPlen;i++)
 {
 result.append("\t"+strPattern.charAt(i));

 }
 result.append("\n");
 for(int i=0;i<gobalPlen;i++)
 {
 result.append("\t"+Integer.toString(prefixTable[i]));

 }
 result.append("\n\n\n");
 }
 //match for KMP
 void matchKmp()
 {
 int i=0,j=0;
 while(i<gobalLen)
 {
 if(strText.charAt(i)==strPattern.charAt(j))
 {
 if(j==gobalPlen-1)
 {
 index=index+"-"+Integer.toString(i-j);
 }else
 {
 i++;
 j++;
 }
 }else if(j>0)
 {
 j=prefixTable[j-1];
 }else
 {
 i++;
 }
 }
 }

//Display
public void display()
{
result.setText("");
result.append("Text:"+strText);
result.append("\nPattern:"+strPattern);
result.append("\nNo of Iteration:"+Integer.toString(iteration));
result.append("\nNo of Comparisons:"+Integer.toString(comparisons));
if(index=="")
{
result.append("\nNo Match Found");
}else
{
result.append("\nMatch Found At\n");


result.append(index.substring(1));

}
result.append("\n--------------------------------------------------------------------\n");

}

}

0 comments:

Post a Comment