I've designed an algorithm to find the longest common subsequence. these are steps:

This is an example:
‫‪

X=A, B, C, B, D, A, B‬‬  
‫‪Y=B, D, C, A, B, A‬‬ 

Pick A in the first string.
Look for A in Y.
Now that there is an A in the second string, append it to common_subsequence.
Return to the first string and pick the next letter that is B. Look for B in the second string this time starting from the position of A.
There is a B after A so append B to common_subsequence.
Now pick the next letter in the first string that is C. There isn't a C next to B in the second string. So assign the value of common_subsequence to lcs because its length is greater than the length of lcs. repeat the previous steps until reaching the end of the first string. In the end the value of lcs is the Longest Common Subsequence.

The complexity of this algorithm is theta(n*m).

I've designed an algorithm to find the longest common subsequence.

These are steps:

This is an example:

X=A, B, C, B, D, A, B‬‬  
‫‪Y=B, D, C, A, B, A‬‬

1. Pick A in the first string.
2. Look for A in Y.
3. Now that there is an A in the second string, append it to common_subsequence.
4. Return to the first string and pick the next letter that is B.
5. Look for B in the second string this time starting from the position of A.
6. There is a B after A so append B to common_subsequence.
7. Now pick the next letter in the first string that is C. There isn't a C next to B in the second string. So assign the value of common_subsequence to lcs because its length is greater than the length of lcs.

Repeat the previous steps until reaching the end of the first string. In the end the value of lcs is the Longest Common Subsequence.

The complexity of this algorithm is \$\theta(n*m)\$.

I implemented it on two methods. The second one is using a hash table, but after implementing I found it's much slower compared to the first algorithm. I can't understand why.

Here are the implementations:

First algorithm:

Second one using hash table:

I implemented it on two methods. The second one is using a hash table, but after implementation I found it's much slower compared to the first algorithm. I can't understand why.

The first algorithm:

The second one using hash table: