public static <E>List<E> lcs(E[] s1, E[] s2) {
		List<E> ret =new LinkedList<E>();
		int x =s1.length, y =s2.length;
		int[][] num =new int[x +1][y +1];
		
		for (int i =1; i <=x; i++)
			for (int j =1; j <=y; j++)
				if (s1[i-1].equals(s2[j-1])) num[i][j] =num[i-1][j-1] +1;
				else num[i][j] =Math.max(num[i-1][j], num[i][j-1]);
		System.out.println("length of LCS =" +num[x][y]);
		
		/*
		for (int[] ii : num) {
			for (int i : ii) System.out.print(i);
			System.out.println();
		}
		*/
		
		while (x >0 && y >0) {
			if (s1[x-1].equals(s2[y-1])) {
				ret.add(s1[x-1]);
				x--; y--;
			}
			else if (num[x][y-1] >num[x-1][y]) y--;
			else x--;
		}
		//for (E e : ret) System.out.print(e);
		//System.out.println();
		Collections.reverse(ret);
		return ret;
	}