AOJ1291 Search of Concatenated Strings

2015/05/15 (Fri) AOJ ローリングハッシュ DP

問題

問題文

文字列の列 $e_1, \cdots , e_n $ と長い文字列 $t$ が与えられる． $e_i$ の全てを $1$ つづ任意の順に結合した文字列は $t$ の部分文字列として何通り含まれるか．

方針

「$dp(i,j) = t$ の $i$ 番目までにビットで表現した集合 $j$ を全て使った文字列が一致している」 とおき，埋めていった． 一致判定を string.substr とか適当にやると TLE するのでローリングハッシュを使った． ロリハを使わなくても AC されている人がいるので理解したい．

実装

bool dp[6000][1<<13];

ll const B = 3;
ull p[6000], thash[6000];
ull shash[13];

int n,m;
int len;
char t[6000];
char ss[13][22];
int sslen[13];

int solve(){
    rep(i,n){
        ull x = 0;
        for(int j=0;ss[i][j];j++){
            x = x*B + ss[i][j];
        }
        shash[i] = x;
    }
    p[0] = 1;
    thash[0] = 0;
    rep(i,len){
        p[i+1] = p[i]*B;
        thash[i+1] = thash[i]*B + t[i];
    }

    rep(i,len+1)rep(j,1<<n) dp[i][j] = false;
    rep(i,len+1) dp[i][0] = true;
    rep(pos,len){
        rep(mask,1<<n){
            if(!dp[pos][mask]) continue;
            rep(i,n){
                if(mask>>i&1) continue;
                if(pos+sslen[i] > len) continue;
                ull h1 = shash[i];
                ull h2 = thash[pos+sslen[i]] - thash[pos] * p[sslen[i]];
                // if(h1 != h2) continue;
                dp[pos+sslen[i]][mask|1<<i] |= h1 == h2; // t.substr(pos,ss[i].size()) == ss[i];
            }
        }
    }

    int ans = 0;
    rep(i,len+1){
        if(dp[i][(1<<n)-1]){
            ++ans;
        }
    }
    return ans;
}

signed main(){
    while(scanf("%d%d",&n,&m), n){
        len = 0;
        rep(i,n){
            scanf("%s",ss[i]);
            sslen[i] = strlen(ss[i]);
        }
        rep(i,m){
            static char buf[22];
            scanf("%s",buf);
            int l = strlen(buf);
            rep(i,l) t[i+len] = buf[i];
            len += l;
        }
        cout << solve() << endl;
    }
}