前几天同学说让我写个字符串匹配,我就想到了KMP,学了下结论很简单,至于证明就没太细看了,结果写完人家说不用了、、、我想着不能白写。so,拍到博客上。
算法讲解:http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
这里讲的简单易懂,反正我看完代码就写出来了。
然后代码附上:
package stringmatch;
import java.util.*;
/** * Created by Lee Y on 2016/5/4. * 应用:kmp算法 */
public final class StringMatch {
public static final StringMatch match = new StringMatch();
private StringMatch(){}
/* 获得字符串匹配表 */
private int[] getMatchList(char[] string){
int l = string.length;
int[] matchList = new int[l];
matchList[0] = 0;
char temp = string[0];
char temp1,current;
int matchValue;
for(int i=1; i<l; i++){
matchValue = matchList[i-1];
current = string[i];
if(matchValue == 0){
if(temp == current){
matchList[i]++;
}
}else{
temp1 = string[matchValue];
if(current == temp1){
matchList[i] = matchValue+1;
}
}
}
return matchList;
}
private boolean match(String matched, String demand, int[] matchList){
int matched_point = 0, demand_point = 0;
int l_matched = matched.length();
int l_demand = demand.length();
char current_matched, current_demand;
int matchedLength = 0, move = 0;
while(matched_point < l_matched && demand_point < l_demand){
current_matched = matched.charAt(matched_point);
current_demand = demand.charAt(demand_point);
if(current_demand == current_matched){
matchedLength++;
matched_point++;
demand_point++;
}else{
move = matchedLength - matchList[demand_point];
if(move != 0){
demand_point -= move;
matchedLength -= move;
}else{
matched_point++;
}
}
if(matchedLength == l_demand){
return true;
}
}
return false;
}
public MatchFactory getMatchFactory(){
return new MatchFactory();
}
public class MatchFactory{
public List getRelateMess(List<String> l, String d){
int[] matchList = getMatchList(d.toCharArray());
for (int i:matchList){
System.out.println(i);
}
List<String> list = new ArrayList<>();
for(String s : l){
if(match(s,d,matchList) == true){
list.add(s);
}
}
return list;
}
}
/* 本类的静态方法可以调用本类的私有构造器 */
public static void main(String[] args) {
StringMatch.MatchFactory sm = match.getMatchFactory();
List<String> list = sm.getRelateMess(l,"我是李灯具,我是李柏炎,我是相许为。");
for (String s : list){
System.out.println(s);
}
}
public static List<String> l = new ArrayList<>();
static {
for(int i=0;i<100000;i++){
l.add("HTML基础语法\n" +
"设计人员,负责设计界面\n" +
"开发人员,拿到界面开始写代码\n" +
"简历用低版本\n" +
"\n" +
"jsp:\n" +
"AS:应用服务器,例如tomcat(服务器集群比较好,把n多服务器当一个服务器用)、jboss(内存上限2g左右)\n" +
"我是李灯具,我是李柏炎,我是相许为。" +
"Servlet:\n" +
"JDBC:数据库连接器 ,JAVA\n" +
"\n");
}
}
}
看懂了应该不难理解,所以没有过多的做注释。