设字符串A的长度为A.length,字符串B的长度为B.length。
Temp[i][j],为状态数组,0<=i<A.length,0=<j<=B.length。
考虑一般情况,如果A[i]==A[j],则Temp[i][j]=Temp[i-1][j-1]+1,
否则Temp[i][j]=0,注:因为求的是连续最长公共字串所以此次为0。
有了状态转移方程,直接写出代码就可以了。
public static int longCommonString(String a, String b) { char[] chsa = a.toCharArray(); char[] chsb = b.toCharArray(); int na = chsa.length; int nb = chsb.length; int[][] t = new int[na][nb]; int max = 0; for (int i = 0; i < na; i++) for (int j = 0; j < nb; j++) { if (i == 0 || j == 0) { if (chsa[i] == chsb[j]) { t[i][j] = 1; if(t[i][j]>max) max=t[i][j]; } } else { if (chsa[i] == chsb[j]) { t[i][j] = t[i - 1][j - 1] + 1; if (t[i][j] > max) { max = t[i][j]; } } } } return max; }