UVA 10192 Vacation

///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / hackerrank / uva / uvalive / spoj), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

#include<bits/stdc++.h>
using namespace std;

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

int lcs(string a, string b)
{
    int al=a.size();
    int bl=b.size();
    int mat[al+2][bl+2];
    CLR(mat);
    for(int i=0;i<al;i++)
        for(int j=0;j<bl;j++)
            if(a[i]==b[j])
                mat[i+1][j+1]=max(max(mat[i+1][j], mat[i][j+1]), mat[i][j]+1);
            else mat[i+1][j+1]=max(max(mat[i+1][j], mat[i][j+1]), mat[i][j]);
return mat[al][bl];
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int kk=1, tc, n;
    string f, m;
    //cin>>tc;
    while(getline(cin,f))
    {
        if(f=="#") return 0;
        getline(cin,m); 
        cout<<"Case #"<<kk++<<": you can visit at most "<< lcs(f, m) <<" cities.\n";
    }

    return 0;
}