LCS.zip_Java LCS_lcs java

import java.util.ArrayList; public class LCS { public static void main(String[] args) { char[] strArray1 = "blue@sina.com".toCharArray(); char[] strArray2 = "www.blue.com".toCharArray(); LCS lcs=new LCS(); ArrayList longestSubStr = lcs.getLongestSubStr(strArray1, strArray2); if (longestSubStr.isEmpty()){ System.out.println("No common substring"); }else{ System.out.println("longest common substring:"+longestSubStr); } } /* return all the longest substrings*/ public ArrayList getLongestSubStr(char[] s1, char[] s2) { int lenS1 = s1.length; int lenS2 = s2.length; int c[][] = new int[lenS1][lenS2];//matrix char[] result; int start, len=0, i, j = 0; ArrayList<Integer> endList=new ArrayList<Integer>(); for (i = 0; i < lenS1; i++) { for (j = lenS2 - 1; j >= 0; j--) { if (s1[i] == s2[j]) { if (i == 0 || j == 0)// special case c[i][j] = 1; else { c[i][j] = c[i - 1][j - 1] + 1;//set value for this position } } else c[i][j] = 0; if (c[i][j] > len) { len = c[i][j]; endList.clear(); endList.add(j); }else if (c[i][j] == len){ endList.add(j);//save the other substrings with the same length. } } } ArrayList resultList=new ArrayList(); for (int end : endList) {//loop for all the longest substrings String strResult=""; start = end - len + 1; for (i = start; i <= end; i++) { strResult = strResult+ s2[i]+""; } resultList.add(strResult); } return resultList; } }