背景
之前做项目,需要做一个文本文件的在线diff.其中用到的就是LCS算法.
今天心血来潮,打算用java写个示例
LCS算法介绍
维基百科的解释
网上的介绍比较多,不细讲
就是用一个二维矩阵来记录两个字符串中所有位置的匹配情况,若是匹配则为1,否则为0.
然后求出对角线最长的1序列，其对应的位置就是最长匹配子串的位置.
当然如果扩展成一个文本文件的话,就是一行一个单位.
这里就不贴图了,直接google,或者看wikipedia里面的图.
代码示例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
| package javaTest;
import junit.framework.Assert;
import org.junit.Test;
public class LCS {
@Test
public void test_lcs() {
String x = "abcdefg";
String y = "fghijklmn";
String lcs = getLCS(x, y);
Assert.assertEquals("fg", lcs);
x = "aaaaaaa";
y = "aaaaaaa";
lcs = getLCS(x, y);
Assert.assertEquals("aaaaaaa", lcs);
x = "abcde";
y = "fghij";
lcs = getLCS(x, y);
Assert.assertEquals("nothing", lcs);
x = "asdfg";
y = "asdjgfhjjhsdfg";
lcs = getLCS(x, y);
Assert.assertEquals("sdfg", lcs);
}
public static String getLCS(String x, String y) {
char[] xc = x.toCharArray();
char[] yc = y.toCharArray();
int xLen = x.length();
int yLen = y.length();
int[][] myArray = new int[xLen][yLen];
int max = 0;
int flag = 0;
for (int i = 0; i < xLen; i++) {
for (int j = 0; j < yLen; j++) {
if (xc[i] == yc[j]) {
if ((i - 1) >= 0 && (j - 1) >= 0) {
myArray[i][j] = myArray[i - 1][j - 1] + 1;
} else {
myArray[i][j] = 1;
}
if (max < myArray[i][j]) {
max = myArray[i][j];
flag = j;
}
} else {
myArray[i][j] = 0;
}
}
}
System.out.println("**********************矩阵图************************");
System.out.println();
System.out.print("#");
for (char c : yc) {
System.out.print(" " + c);
}
System.out.println("");
for (int i = 0; i < xLen; i++) {
System.out.print(xc[i]);
for (int j = 0; j < yLen; j++) {
System.out.print(" " + myArray[i][j]);
}
System.out.println("");
}
if (max >= 2) {
return (y.substring((flag + 1) - max, flag + 1));
} else {
return "nothing";
}
}
public static void printMatrixNoIncrement(String x, String y) {
char[] xc = x.toCharArray();
char[] yc = y.toCharArray();
int xLen = x.length();
int yLen = y.length();
int[][] myArray = new int[xLen][yLen];
for (int i = 0; i < xLen; i++) {
for (int j = 0; j < yLen; j++) {
if (xc[i] == yc[j]) {
myArray[i][j] = 1;
} else {
myArray[i][j] = 0;
}
}
}
System.out.print("#");
for (char c : yc) {
System.out.print(" " + c);
}
System.out.println("");
for (int i = 0; i < xLen; i++) {
System.out.print(xc[i]);
for (int j = 0; j < yLen; j++) {
System.out.print(" " + myArray[i][j]);
}
System.out.println("");
}
}
}
|