Editing Longest common subsequence (section)

=== ''LCS'' function defined ===
Let two sequences be defined as follows:  <math>X=(x_1 x_2 \cdots x_m)</math> and <math>Y=(y_1 y_2 \cdots y_n)</math>.  The prefixes of <math>X</math> are <math>X_0, X_1, X_2, \dots, X_m</math>; the prefixes of <math>Y</math> are <math>Y_0, Y_1, Y_2, \dots, Y_n</math>.  Let <math>\mathit{LCS}(X_i,Y_j)</math> represent the set of longest common subsequence of prefixes <math>X_i</math> and <math>Y_j</math>.  This set of sequences is given by the following.

:<math>
\mathit{LCS}(X_i,Y_j)=\begin{cases}
  \epsilon & \mbox{if }i=0\mbox{ or }j=0 \\
  \mathit{LCS}(X_{i-1},Y_{j-1}) \hat{} x_i & \mbox{if }i,j>0\mbox{ and }x_i=y_j \\
  \operatorname{\max}\{\mathit{LCS}(X_i,Y_{j-1}),\mathit{LCS}(X_{i-1},Y_j)\} & \mbox{if }i,j>0\mbox{ and }x_i\ne y_j.
\end{cases}
</math>

To find the LCS of <math>X_i</math> and <math>Y_j</math>, compare <math>x_i</math> and <math>y_j</math>.  If they are equal, then the sequence <math>\mathit{LCS}(X_{i-1},Y_{j-1})</math> is extended by that element, <math>x_i</math>.  If they are not equal, then the longest among the two sequences, <math>\mathit{LCS}(X_i,Y_{j-1})</math>, and <math>\mathit{LCS}(X_{i-1},Y_j)</math>, is retained.  (If they are the same length, but not identical, then both are retained.) The base case, when either <math>X_i</math> or <math>Y_i</math> is empty, is the [[empty string]], <math>\epsilon</math>.