我用100*100的陣列紀錄竟然AC了...

566686

x000032001

c001. 最長共同字串

AC (4ms, 782KB)

[B@9b619cC++

2010-09-18 16:46

#include <iostream>
#include <string>
#define max(x,y) (x>y)?(x):(y)
using namespace std;

int main()
{
    string sa,sz;
    int dp[100][100];
    while( 1 )
    {
        getline(cin,sa);
        getline(cin,sz);
        for(int i = 0 ; i<100; ++i )
            for(int j = 0 ; j<100; ++j )
                dp[i][j] = 0;
        for(int i = 0 ; i<sa.size() ; ++i )
        {
            for(int j = 0 ; j<sz.size() ; ++j )
            {
                if(sa[i] == sz[j])
                    dp[i+1][j+1] = dp[i][j] + 1;
                else
                    dp[i+1][j+1] = max(dp[i][j+1] , dp[i+1][j]);
            }
        }
        if(!cin.eof())
            cout << dp[sa.size()][sz.size()] << endl;
        else
            return 0;
    }
    return 0;
}

輸入說明 ：

事實上還不到50

XD