# Longest Common Subsequences
p.s. 有空再來寫詳細的過程
(Time Limit: 1 second)
## Problem Description
Please find the length of a longest common subsequence of two given nonempty strings.
## Input Format
Each test case contains two nonempty strings, separated by whitespace character(s) and consisting of characters 'a' and 'b'. Two consecutive test cases are separated by whitespace character(s). The input terminates with EOF.
## Output Format
For each test case, output the length of a longest common subsequence of the two given strings.
## Technical Specification
* There are at most 10 test cases.
* Each string to be processed is at most 100 in length.
## Example

## 看題目送code
我人真好～

#include <iostream>
#include <string>
using namespace std;

int LCS(string s1, string s2)
{
    int** map = new int*[s2.size()+1];
    for(int i=0;i<s2.size()+1;i++)
        map[i] = new int[s1.size()+1];
    for(int i=0;i<s2.size()+1;i++)
        map[i][0] = 0;
    for(int j=0;j<s1.size()+1;j++)
        map[0][j] = 0;
    for(int j=1;j<s2.size()+1;j++)
    {
        for(int i=1;i<s1.size()+1;i++)
        {
            if(s1[i-1]==s2[j-1])
                map[j][i]=map[j-1][i-1]+1;
            else
            {
                if(map[j-1][i]>map[j][i-1])
                    map[j][i]=map[j-1][i];
                else
                    map[j][i]=map[j][i-1];
            }
            cout << map[j][i] << " ";
        }
        cout << endl;
    }
    int answer = map[s2.size()][s1.size()];
    for(int i=0;i<=s2.size();i++)
        delete map[i];
    delete[] map;
    return answer;
}

int main()
{
    int answer[10]; //putting the answer of LCS
    int counter = 0;
    string s1;
    string s2;
    while(counter<10 && cin >> s1)
    {
        if(s1[0]==EOF)
            break;
        cin >> s2;
        if(s2[0]==EOF)
            break;
        answer[counter] = LCS(s1,s2);
        counter++;
        //s1.clear();
        //s2.clear();
    }
    for(int i=0;i<counter;i++)
        cout << answer[i] << endl;
    return 0;
}

###### tags:`演算法` `cpp` `Awwwolf的刷題之路`