Longest Common Continuous Subarray

输入：

[
  ["3234.html", "xys.html", "7hsaa.html"], // user1
  ["3234.html", "sdhsfjdsh.html", "xys.html", "7hsaa.html"] // user2
]

输出两个user的最长连续且相同的访问记录。

["xys.html", "7hsaa.html"]

Solution:

和LCS https://leetcode.com/problems/longest-common-subsequence/做法类似，如果当前两个string相等就把当前格子变成[i - 1][j - 1] + 1。不相等就保留0。

https://app.gitbook.com/s/-M33ghpQv0ZbnP8UX-Qg/9.dynamic-programming/1143.-longest-common-subsequence-m https://www.geeksforgeeks.org/longest-common-subarray-in-the-given-two-arrays/#:~:text=Given%20two%20arrays%20A%5B%5D,between%20the%20two%20given%20array. Same as https://leetcode.com/problems/maximum-length-of-repeated-subarray/

    public String[] longestCommonContinuousHistory(String[] history1, String[] history2)
    {
        int s1 = history1.length;
        int s2 = history2.length;
        
        int count = Integer.MAX_VALUE;
        int startIndex = 0;
        //int endIndex = 0;
        
        int[][] dp = new int[s1+1][s2+1];
        for(int i = 0; i<=s1; i++)
        {
            dp[i][0] = 0;
        }
        for(int j = 0; j<=s2; j++)
        {
            dp[0][j] = 0;
        }
        
        for(int i = 1; i<=s1; i++)
        {
            for(int j = 1; j<=s2; j++)
            {
                if(history1[i] == history2[j])
                {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else
                {
                    dp[i][j] = 0;
                }
                
                
                if(dp[i][j] > count)
                {
                    count = dp[i][j];
                    startIndex = i-count;
                    //endIndex = i;
                }
            }
        }
        
        String[] result = new String[count];
        int index = 0;
        while(index < count)
        {
            result[index] = history1[startIndex];
            index++;
            startIndex++;
        }
        
        return result;
    }