String matching algorithm
Hi all,
I have a problem to make a pattern string matching animation. It call "Brute Force Animation", "Knuth-Morris-Pratt", and Boyer-Moore Algorithm". The idea is to drawing animation which is sufficient for all string matching animation.
I do The process in Brute Force Algorithm is to compare every character in two string which are given. When the character in source String and pattern string is mismatch, so they will set the colour as red and the pattern String will move to the right otherwise it will be green.
My idea is to run the animation and also the pseudo code, which you could see in my code (when you compile it). My problem is, I don't know how to make patternString (mPatternString) move to the right, and make running the pseudo code together with string animation when the button "Run" click, also I have a problem in colouring the character.
Please help me to fix my code and could you tell me the algorithm how to do it.
package hai;
import java.awt.Color;
import java.awt.Container;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.GridBagConstraints;
import java.awt.GridBagLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.Comparator;
import javax.swing.BorderFactory;
import javax.swing.JButton;
import javax.swing.JComboBox;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JList;
import javax.swing.JPanel;
import javax.swing.JTextArea;
import javax.swing.SwingConstants;
import javax.swing.border.Border;
/**
*
* @author amelia
* update terbaru
*
*/
publicclass MainStringFrame1{
publicstaticvoid main(String[] args){
AnimationStringFrame1 frame =new AnimationStringFrame1();
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.setVisible(true);
}
}
class AnimationStringFrame1extends JFrame
{
publicstaticfinalint DEFAULT_WIDTH = 1000;
publicstaticfinalint DEFAULT_HEIGHT = 500;
/** constants for predefined colors */
privatestaticfinal Color lightBlue =new Color(153, 204, 255);
private JTextArea ngaco;
private JButton tombolRun;
private JButton tombolStep;
private StringPanelArray1 mStringArray;
/**adding combo box at 05 July 2007
final static String[] searchedMethod = {"Brute-Force","Knuth-Morris-Pratt","Boyer-Moore"} ;
private JLabel lblAlg;
private JComboBox combo;
private JPanel firstPanel;
**/
public AnimationStringFrame1()
{
setTitle("Brute Force Algorithm");
setSize(DEFAULT_WIDTH,DEFAULT_HEIGHT);
Container contentPane = getContentPane();
GridBagLayout layout =new GridBagLayout();
contentPane.setLayout(layout);
contentPane.setBackground(lightBlue);
//construct components
JLabel faceLabel =new JLabel("Brute Force Algorithm", SwingConstants.CENTER);
ngaco =new JTextArea();
ngaco.setText("Untuk tempat animasi");
ngaco.setEditable(false);
String bruteForceCode[] ={
"int count = 0",//0
"int m= mPattern.length();",//1
"int n= mSource .length();",//2
"outer:",//3
"for (int i = 0; i <= n - m; ++i) {",//4
"for (int k = 0; k < m; ++k) {",//5
"if (mPattern.charAt(k) != mSource.charAt(i + k)) {",//6
"continue outer;",//7
" }",//8
" }",//9
"++count;",//10
"}",//11
"return count;",//12
"}"//13
};
JList list =new JList(bruteForceCode);// a container for pseudo code
//Set the size and border of list (JList component)
Border etch = BorderFactory.createEtchedBorder();
list.setBorder(BorderFactory.createTitledBorder(etch,"Brute Force Code"));
tombolRun =new JButton("Run");
tombolStep =new JButton("Step");
//add components to grid
GridBagConstraints constraints =new GridBagConstraints();
//label itu
constraints.fill = GridBagConstraints.HORIZONTAL;
constraints.weightx = 0.5;
constraints.weighty = 1;
constraints.gridx = 0;
constraints.gridy = 0;
contentPane.add(faceLabel, constraints);
faceLabel.setOpaque(true);
faceLabel.setBackground(new Color(153, 204, 255));
mStringArray =new StringPanelArray1();
//ngaco
constraints.fill = GridBagConstraints.BOTH;
constraints.weightx = 0.0;
constraints.gridwidth = 2;
constraints.gridx = 0;
constraints.gridy = 1;
contentPane.add(mStringArray, constraints);
//Animasi
constraints.fill = GridBagConstraints.VERTICAL;
constraints.gridx = 1;
constraints.gridy = 1;
constraints.gridheight = 1;
constraints.gridwidth = 2;
contentPane.add(list, constraints);
//button Run
constraints.fill = GridBagConstraints.NONE;
constraints.gridx = 0;
constraints.gridy = 2;
constraints.weightx = 1;
constraints.weighty = 1;
contentPane.add(tombolRun, constraints);
//button Step
constraints.fill = GridBagConstraints.NONE;
constraints.weightx = 1;
constraints.weighty = 1;
constraints.gridx = 1;
constraints.gridy = 2;
contentPane.add(tombolStep, constraints);
tombolRun.addActionListener(new ActionListener()
{
publicvoid actionPerformed (ActionEvent event)
{
startAnimation();
}
});
tombolStep.addActionListener(new ActionListener()
{
publicvoid actionPerformed (ActionEvent event)
{
stopAnimation();
}
});
}
publicvoid startAnimation()
{
mStringArray.finish =false;
mStringArray.start();
}
publicvoid stopAnimation()
{
}
}
/** Program untuk menggambar * */
class StringPanelArray1extends JPanelimplements Runnable{
private String mSourceString ="GCATCGCAGAGAGT";
private String mPatternString ="GCAGAGAG";
private String mFirstSource;
private String mSecondPattern;
privateint xPosSource = 40;
privateint yPosSource = 30;
privateint xPosPattern = 40;
privateint yPosPattern = 80;
private Thread thread;
privateint count = 0;
publicboolean finish;
private Comparator<Character> mComparator;// an object to compare two values
publicvoid paintComponent(Graphics g){
super.paintComponent(g);
Graphics2D g2 = (Graphics2D) g;
setBackground(new Color(153, 204, 255));
paintRectangle(g2,false);
paintRectangleSource(g2, 3,false);
}
privatevoid paintRectangle(Graphics2D g2,boolean foundString)
{
int xPosSourceTemp = xPosSource;
int yPosSourceTemp = yPosSource;
int xPosPatternTemp = xPosPattern;
int yPosPatternTemp = yPosPattern;
if (foundString){
g2.setColor(Color.RED);
}else{
g2.setColor(Color.BLUE);
}
for (int i = 0; i < mSourceString.length(); i++)
{
g2.drawRect(xPosSourceTemp, yPosSourceTemp, 25, 25);
g2.drawString(mSourceString.charAt(i) +"", xPosSourceTemp +10, yPosSourceTemp +15);
xPosSourceTemp += 25;
}
for (int i = 0; i < mPatternString.length(); i++)
{
g2.drawRect(xPosPatternTemp, yPosPatternTemp, 25, 25);
g2.drawString(mPatternString.charAt(i) +"", xPosPatternTemp +10, yPosPatternTemp +15);
xPosPatternTemp += 25;
}
}
privatevoid paintRectangleSource(Graphics2D g2,int i,boolean found)
{
int xPosSourceTemp = xPosSource;
int yPosSourceTemp = yPosSource;
int xPosPatternTemp = xPosPattern;
int yPosPatternTemp = yPosPattern;
if (!found){
g2.setColor(Color.RED);
}else{
g2.setColor(Color.GREEN);
}
for (int j = 0; j < mSourceString.length(); j++)
{
if (i == j){
g2.fillRect(xPosSourceTemp, yPosSourceTemp, 25, 25);
g2.setColor(Color.BLACK);
g2.drawString(mSourceString.charAt(i) +"", xPosSourceTemp +10, yPosSourceTemp +15);
}
xPosSourceTemp += 25;
}
}
publicvoid start(){
thread =new Thread(this);
thread.start();
}
publicsynchronizedvoid stop(){
thread =null;
}
publicvoid run(){
Thread me = Thread.currentThread();
while (this.thread == me && !this.finish)
{
Graphics2D g2 = (Graphics2D) getGraphics();
paint(g2,"Brute-Force");
g2.dispose();
thread.yield();
}
thread =null;
}
publicvoid paint(Graphics g, String algorithm)
{
Graphics2D g2 = (Graphics2D)g;
g2.setColor(Color.BLACK);
this.count = 0;
if(algorithm =="Brute-Force"){
System.out.println("Start Brute-Force");
int m = mPatternString.length();
int n = mSourceString.length();
outer:
for (int i = 0; i <= n - m; ++i){
for (int k = 0; k < m; ++k){
if(!this.finish){
if (mPatternString.charAt(k) != mSourceString.charAt(i + k)){
paintRectangle(g2,true);
paintRectangleSource(g2, i,true);
//delay
try{
Thread.sleep(1000);
}catch(InterruptedException e){}
continue outer;
}else{
paintRectangle(g2,false);
//delay
try{
Thread.sleep(1000);
}catch(InterruptedException e){}
}
}
}
++count;
}
System.out.println("finish Brute-Force");
this.finish =true;
}
}
}
[/code[code]
]
