SRM519 Div1 Medium(600) RequiredSubstrings

RequiredSubstrings

動的計画法。それぞれの位置で各文字列の一致長ごとに条件を満たす文字列の個数を覚えておく。計算量が50⁷くらいになりそうだけど、実際はそんなに大きくならないらしい。

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

vector<string> words;
int N, C, L;
//  T[i][j][k]:
//  　i番目の文字列がj文字一致していて次の文字kが来た場合に、
//  　何文字一致するか。一度文字列が出現したら文字列長
int T[6][51][128];
map<long long,int> memo[50];

//  p: 現在位置
//  l: それぞれの文字列の一致長
int BT( int p, vector<int> l )
{
    if ( p >= L )
    {
        int c = 0;
        for ( int i=0; i<N; i++ )
            if ( l[i]==(int)words[i].length() )
                c++;
        return (int)(c==C);
    }

    long long key = 0;
    for ( int i=0; i<N; i++ )
        key = key*50+l[i];
    if ( memo[p].count(key) > 0 )
        return memo[p][key];

    long long ans = 0;

    for ( char c='a'; c<='z'; c++ )
    {
        vector<int> t(N);
        for ( int i=0; i<N; i++ )
            t[i] = T[i][l[i]][c];
        ans += BT( p+1, t );
        ans %= 1000000009;
    }

    return memo[p][key] = (int)ans;
}

class RequiredSubstrings{public:
int solve( vector <string> words, int C, int L )
{
    ::words = words;
    ::N = (int)words.size();
    ::C = C;
    ::L = L;

    for ( int i=0; i<N; i++ )
    {
        int l = (int)words[i].length();
        for ( int j=0; j<l; j++ )
        for ( char c='a'; c<='z'; c++ )
        {
            string s = words[i].substr(0,j)+c;
            for ( int k=0; k<=(int)s.length(); k++ )
                if ( words[i].substr(0,k) == s.substr(s.length()-k) )
                    T[i][j][c] = k;
        }
        for ( char c='a'; c<='z'; c++ )
            T[i][words[i].length()][c] = l;
    }

    for ( int i=0; i<L; i++ )
        memo[i].clear();

    return BT( 0, vector<int>(N) );
}};