📄 ldframe.java
字号:
//列文斯顿距离算法
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
public class LDFrame extends JFrame implements ActionListener {
Label source=new Label("模板字符串");
Label target=new Label("匹配字符串");
Label distance=new Label("两者间距离");
TextField sourt=new TextField(10);
TextField targt=new TextField(10);
TextField dist=new TextField(5);
Button button=new Button("计算");
String sous=new String("");
Label a=new Label(" ");
Label b=new Label(" ");
Label c=new Label(" ");
String tars=new String("");
EditPanel panel =new EditPanel();
int ld;
int d[][];
int[][] dp=new int[13][13];
int[][] scost=new int[13][13];
int[] xp=new int[8];
int[] yp=new int[8];
int[] tracex =new int[13];
int[] tracey =new int[13];
int xt;
int yt;
int it;
int pointer;
/* 构造函数*/
public LDFrame() {
setTitle("列文斯顿距离--算法");
setSize(new Dimension(800, 600));
Container contentPane=getContentPane();
contentPane.add(panel);
source.setLocation(100,600);
panel.add(source);
panel.add(sourt);
sourt.setBackground(Color.lightGray);
panel.add(a);
panel.add(target);
panel.add(targt);
targt.setBackground(Color.lightGray);
panel.add(b);
panel.add(distance);
panel.add(dist);
dist.setBackground(Color.lightGray);
panel.add(button);
panel.add(c);
button.addActionListener(this);
this.addWindowListener
(
new WindowAdapter() {
public void windowClosing(WindowEvent e) {
LDFrame.this.windowClosed();
}
}
);
}
protected void windowClosed() {
System.exit(0);
}
public void actionPerformed(ActionEvent e)
{
Object sc=e.getSource();
if(sc== button)
{
pointer=0;
sous=sourt.getText();
tars=targt.getText();
ld=LD(sous,tars);
dist.setText(String.valueOf(ld));
trace();
panel.repaint();
}
}
private int Min(int a, int b, int c) {
int mi;
mi = a;
if (b < mi) {
mi = b;
}
if (c < mi) {
mi = c;
}
return mi;
}
public int LD (String s, String t) {
int n;
int m;
int i;
int j;
char s_i;
char t_j;
int cost;
// 第一步
n = s.length ();
m = t.length ();
if (n == 0) {
return m;
}
if (m == 0) {
return n;
}
d = new int[n+1][m+1];
// 第二步
for (i = 0; i <= n; i++) {
d[i][0] = i;
}
for (j = 0; j <= m; j++) {
d[0][j] = j;
}
for(int p=0;p<12;p++)
{
for(int pp=0;pp<12;pp++)
{
dp[p][pp]=0;
scost[p][pp]=0;
}
}
for(int p=0;p<12;p++)
{
dp[p][0]=1;
dp[0][p]=2;
}
// 第三步
for (i = 1; i <= n; i++) {
s_i = s.charAt (i - 1);
// 第四步
for (j = 1; j <= m; j++) {
t_j = t.charAt (j - 1);
// 第五步
if (s_i == t_j) {
cost = 0;
scost[i][j]=0;
}
else {
cost = 1;
scost[i][j]=1;
}
// 第六步
d[i][j] = Min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + cost);
if(d[i][j]==(d[i-1][j]+1))
{
dp[i][j]=1;
}
else if(d[i][j]==d[i][j-1]+1)
{
dp[i][j]=2;
}
else if(d[i][j]==d[i-1][j-1] + cost)
{
dp[i][j]=3;
}
}
}
//第七步
for(int z=0;z<n;z++)
{
for(int l=0;l<m;l++)
{
System.out.print(d[z][l]);
}
System.out.println();
}
return d[n][m];
}
public void trace()
{
int n=sous.length();
int m=tars.length();
int tx=n;
int ty=m;
int stop=0;
tracex[0]=100+50*n;
tracey[0]=500-50*m;
for(int i=1;i<=12;i++)
{
tracex[i]=0;
tracey[i]=0;
}
for(int p=0;p<9;p++)
{
for(int pp=0;pp<9;pp++)
{
System.out.print(dp[p][pp]);
}
System.out.println();
}
System.out.println();
for(int p=0;p<9;p++)
{
for(int pp=0;pp<9;pp++)
{
System.out.print(scost[p][pp]);
}
System.out.println();
}
while(!((tx==0)&&(ty==0)))
{
switch(dp[tx][ty])
{
case 1:{
System.out.println(tx+""+ty+" 1");
pointer++;
tracex[pointer]=100+50*(tx-1);
tracey[pointer]=500-50*ty;
tx=tx-1;
System.out.print(tx);
System.out.println(ty);
break;
}
case 2:{
System.out.println(tx+""+ty+" 2");
pointer++;
tracex[pointer]=100+50*tx;
tracey[pointer]=500-50*(ty-1);
ty=ty-1;
System.out.print(tx);
System.out.println(ty);
break;
}
case 3:
{
System.out.println(tx+""+ty+" 3");
pointer++;
tracex[pointer]=100+50*(tx-1);
tracey[pointer]=500-50*(ty-1);
tx=tx-1;
ty=ty-1;
System.out.print(tx);
System.out.println(ty);
break;
}
}
stop++;
if(stop==7)
break;
}
}
class EditPanel extends JPanel
{
public void paintComponent(Graphics g)
{
super.paintComponent(g);
this.setBackground(Color.darkGray);
Graphics2D g2=(Graphics2D)g;
g2.setColor(Color.blue);
for(int i=1;i<12;i++)
{
g2.drawLine(100+i*50,500,100+i*50,100);
}
for(int j=1;j<8;j++)
{
g2.drawLine(100,500-j*50,700,500-j*50);
}
for(int k=0;k<sous.length();k++)
{
g2.drawString(String.valueOf(sous.charAt(k)),148+k*50,520);
}
for(int l=0;l<tars.length();l++)
{
g2.drawString(String.valueOf(tars.charAt(l)),80,455-l*50);
}
g2.drawString("匹配字符串",10,100);
g2.drawString("模板字符串",710,520);
g2.setStroke(new BasicStroke(3f,BasicStroke.CAP_ROUND,BasicStroke.JOIN_MITER));
g2.drawLine(100,500,700,500);
g2.drawLine(100,500,100,100);
g2.drawLine(105,105,100,100);
g2.drawLine(695,495,700,500);
g2.setColor(Color.red);
g2.setStroke(new BasicStroke(5f,BasicStroke.CAP_ROUND,BasicStroke.JOIN_MITER));
drawtrace(sous.length(),tars.length(),g2);
}
public void drawtrace(int tx,int ty,Graphics2D g2)
{
if((tx==0)&&(ty==0))
return;
else if((tx==0)&&(ty!=0))
{
g2.drawLine(100+tx*50,500-ty*50,100+tx*50,500-(ty-1)*50);
drawtrace(tx,ty-1,g2);
}
else if((ty==0)&&(tx!=0))
{
g2.drawLine(100+tx*50,500-ty*50,100+(tx-1)*50,500-ty*50);
drawtrace(tx-1,ty,g2);
}
else
{
if(d[tx][ty]==(d[tx-1][ty]+1))
{
System.out.println(tx+" "+ty+"to"+(tx-1)+" "+ty);
System.out.println("in1");
g2.drawLine(100+tx*50,500-ty*50,100+(tx-1)*50,500-ty*50);
drawtrace(tx-1,ty,g2);
}
if(d[tx][ty]==(d[tx][ty-1]+1))
{
System.out.println(tx+" "+ty+"to"+tx+" "+(ty-1));
System.out.println("in2");
g2.drawLine(100+tx*50,500-ty*50,100+tx*50,500-(ty-1)*50);
drawtrace(tx,ty-1,g2);
}
if(d[tx][ty]==(d[tx-1][ty-1] + scost[tx][ty]))
{
System.out.println(tx+" "+ty+"to"+(tx-1)+" "+(ty-1));
System.out.println("in3");
g2.drawLine(100+tx*50,500-ty*50,100+(tx-1)*50,500-(ty-1)*50);
drawtrace(tx-1,ty-1,g2);
}
}
}
}
}⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -