首页 > 代码库 > 经典算法回顾2
经典算法回顾2
public class Main1 { static String s1 = "abcd"; static String s2 = "abce"; public static void main(String[] args) { // TODO Auto-generated method stub /* * 字符串相似度 * 概念： * 对于两个字符串A和B，通过基本的增删改将字符串A改成B，或者将B改成A， * 在改变的过程中使用的最小步骤称之为“编辑距离” */ System.out.println(LD()); } public static int LD(){ int a[][] = new int[s1.length()+1][s2.length()+1]; for(int i = 0; i <= s1.length(); i++){ a[i][0] = i; } for(int j = 0; j <= s2.length(); j++){ a[0][j] = j; } for(int i = 1; i <= s1.length(); i++){ for(int j = 1; j <= s2.length(); j++){ if(s1.getBytes()[i-1] == s2.getBytes()[j-1]){ a[i][j] = a[i-1][j-1]; } else{ int temp = Math.min(a[i-1][j], a[i][j-1]); a[i][j] = Math.min(temp, a[i-1][j-1]) + 1; } } } return a[s1.length()][s2.length()]; }}
public class Main2 { public static void main(String[] args) { // TODO Auto-generated method stub /* * KMP算法 */ String str1 = "ababcabababdc"; String str2 = "abc"; System.out.println("fff"); int index = KMP(str1,str2); System.out.println(index); } static int KMP(String str1, String str2){ int i = 0; int j = 0; int[] next = new int[str2.length()]; next = GetNextVal(str2); while(i < str1.length() && j < str2.length()){ if(j == -1 || str1.getBytes()[i] == str2.getBytes()[j]){ i++; j++; } else{ j = next[j]; } } if(j == str2.length()){ return i - str2.length(); } return -1; } static int[] GetNextVal(String str2){ int k= -1; int j = 0; int[] next = new int[str2.length()]; next[j] = -1; while(j < str2.length() -1){ if(k == -1 || str2.getBytes()[k] == str2.getBytes()[j]){ next[++j] = ++k; } else{ k = next[k]; } } return next; }}
经典算法回顾2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。