SRM488 Div1 Medium(500) TheBoringStoreDivOne

TheBoringStoreDivOne

u,v∈Σ⁺, x∈Σ^*として、A=ux, B=u, C=v, D=xvと書ける。uとvが影響し合うことはないので、各xについて最も長いuを覚えておく。

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

bool cmp( string a, string b )
{
    return a.length() < b.length()  ||
           a.length() == b.length()  &&  a > b;
}

class TheBoringStoreDivOne{public:
string find( string J, string B )
{
    int n = (int)J.length();
    int m = (int)B.length();

    map<string,string> M;
    for ( int i=0; i<n; i++ )
        for ( int j=0; i+j<=n; j++ )
            M.insert( make_pair( J.substr(i,j), "" ) );
    for ( int i=0; i<m; i++ )
        for ( int j=0; i+j<=m; j++ )
            M.insert( make_pair( B.substr(i,j), "" ) );

    for ( int i=0; i<n; i++ )
    for ( int j=i+1; j<n; j++ )
    for ( int k=1; i+k<=j && j+k<=n && J[i+k-1]==J[j+k-1]; k++ )
    {
        for ( int l=0; i+k+l<=j; l++ )
        {
            string x = J.substr(i+k,l);
            M[x] = max( M[x], J.substr(i,k), cmp );
        }
        for ( int l=0; j+k+l<=n; l++ )
        {
            string x = J.substr(j+k,l);
            M[x] = max( M[x], J.substr(j,k), cmp );
        }
    }

    string ans = "";

    for ( int i=0; i<m; i++ )
    for ( int j=i+1; j<m; j++ )
    for ( int k=1; 0<=i-k+1 && i<=j-k && B[i-k+1]==B[j-k+1]; k++ )
    {
        for ( int l=0; 0<=i-k-l+1; l++ )
        {
            string x = B.substr(i-k-l+1,l);
            if ( M[x] != "" )
                ans = max( ans, M[x]+x+B.substr(i-k+1,k), cmp );
        }
        for ( int l=0; i<=j-k-l; l++ )
        {
            string x = B.substr(j-k-l+1,l);
            if ( M[x] != "" )
                ans = max( ans, M[x]+x+B.substr(j-k+1,k), cmp );
        }
    }

    return ans; 
}};