Lets us define the next recursive expression: the longest common sub-string of . So our solution will be
- - A definition for empty words.
- in case or otherwise.
- Start an matrix full with 's.
- Fill the matrix diagonally (right to left diagonals starting at then , then and do forth ) using the expressions (pay attention that are already filled).In addition: at each time when save the pair (those pairs are the sub-string's indexes in respectively).
- Return , and the sub-string formed from the saved indexes.
Complexity time, space.
- Let us prove by induction that for all , values is correct.
- Base case: so, for all the longest common sub-string is the empty string from length , and is defined to be as needed.
- Assumption: for all and *for all* holds the correct values.
- Step: (now we start an induction over j values when through the whole induction process).
- Base: as explained before the longest common sub-string is from length , and (as defined).
- Assumption : for all we assume holds the right value.
- In case : the longest common sub-string can't include both so the longest common sub-string is the maximal between the longest sub-string formed from or from . In this case, the induction's assumption promises holds the correct values, so is the correct value.
- In case , let us assume there exists a common sub-string such that -:
- in case is formed from the indexes from respectively, then when is formed from the indexes from our induction assumption we know that therefore which contradicts the assumption.
- in case is formed from and not from (means a couple for is taken from then by the induction assumption, Now we need to make the last observation: , this holds due to the fact that in one may take at list one indexes pair which doesn't appear in which is an indexes pair of the form , thus by adding to we may bound the difference of . So in conclusion so this contradicts existence.
- The case of is formed from but not from is symmetric.
This finishes the prove.