package codingInterviewGuide.part4dp;

/**最长公共子串,得用dp去做
 * Created by Dell on 2017年08月10日.
 */
public class LongestSubstring {
 public int findLongest2(String A, int n, String B, int m) {
 int[][] dp=new int[n+1][m+1];
 char[] a=A.toCharArray();
 char[] b=B.toCharArray();
 int len=-1;
 for(int i=0;i<n;i++){
 for(int j=0;j<m;j++){
 if(a[i]==b[j]){
 dp[i+1][j+1]=dp[i][j]+1;
 len=Math.max(len,dp[i+1][j+1]);
 }
 }
 }
 return len;
 }
 public int findLongest(String A, int n, String B, int m) {
// int[][] dp=new int[n+1][m+1];
 char[] a=A.toCharArray();
 char[] b=B.toCharArray();
 int len=0,cura=0,curb=0,curlen=0;//按照斜线计算,可将空间压缩至O(1)
 //将矩阵上半区统计
 for(int j=0;j<m+n;j++){
 if(j<n){
 cura=j;curb=0;
 }else{
 cura=0;curb=j-n;
 }
 curlen=0;
 while(cura<n&&curb<m){//从a串第一个字符开始比较,直至其中一个字符超出
 if(a[cura]==b[curb]){
 curlen+=1;len=Math.max(len,curlen);
 }else{
 curlen=0;
 }cura++;curb++;
 }
 }
 return len;
 }
}