public class OnlineTestLCS {
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		try {
			int r;

			r = FindLCS("ababcababababcabcab", "abcabcabc", 4);
			System.out.printf("LCS %s\n", r);

			r = FindLCS("abababababababab", "ababcabc", 2);
			System.out.printf("LCS %s\n", r);

			r = FindLCS("abababababababab", "abcabccabc", 2);
			System.out.printf("LCS %s\n", r);

		} catch (Exception e) {
			e.printStackTrace();
		}
	}

    static int FindLCS(String strA, String strB, int minLength)
    {
        if (strA.length() < strB.length())
            return FindLCS(strB, strA, minLength);

        if (strB.length() == 0)
        	return 0;


        minLength = Math.max(1, minLength);
        int r = 1 + minLength;
    	int[][] ML = new int[r][];
    	for(int i = 0; i < r; i++)
    		ML[i] = new int[strB.length()];

        int length = 0;
    	int[] SL = new int[strB.length()];

    	int m;
        for (int i = 0; i < strA.length(); ++i)
        {
        	// First fill current sequence length
            char chr = strA.charAt(i);
            for (int j = strB.length(); --j > 0;)
            {
                SL[j] = (chr == strB.charAt(j) ? 1 + SL[j - 1] : 0);
            }
            SL[0] = (chr == strB.charAt(0) ? 1 : 0);

            //Update matches
            ML[i % r][minLength - 1] = m = (SL[minLength - 1] == minLength ? minLength : ML[(i + minLength) % r][minLength - 1]);
        	if(length < m)
        	{
        		length = m;
        		if(m == strB.length())
        			return length;
        	}

            for (int j = minLength; j < strB.length(); ++j)
            {
        		// i + minLength == i - 1 : mod r
        		// i - minLength == i + 1 : mod r
            	if(SL[j] == minLength)
            	{
            		m = minLength + ML[(i + 1) % r][j - minLength];
            	}
            	else if(SL[j] > minLength)
            	{
            		m = Math.max(1 + ML[(i - 1) % r][j - 1], minLength + ML[(i + 1) % r][j - minLength]);
            	}
            	else
            	{
            		m = Math.max(ML[(i + minLength) % r][j], ML[i % r][j - 1]);
            	}
            	ML[i % r][j] = m;
            	if(length < m)
            	{
            		length = m;
            		if(m == strB.length())
            			return length;
            	}
            }
        }
        return length;
    }

}