AOJ 1291 : Search of Concatenated Strings
問題リンク:Search of Concatenated Strings | Aizu Online Judge
問題概要:
n個(1 <= n <= 12)の文字列と長さが1以上5000以下の文字列tが与えられる
n個の文字列を任意の順で全てつなげた文字列がtのなかにどのくらい存在するか?
ただし、n個の文字列をつなげた際に同じものが複数できた場合はそれらを1つとみなす
解法:
動的計画法だった
KMPでやれないかと考えていたが、できなさそうなので諦め
dpする際のループで毎回文字列を比較しているとTLEになるので
あらかじめisAble[tのインデックス][n個の文字列のうちどれか] := true or false
みたいなのを作っておいて判定しなければならない
コード:
int n,m; string e[MAX_E]; string text; bool dp[5001][(1<<12)]; bool isAble[5001][12]; int main() { int tmp; while(tmp = scanf("%d %d",&n,&m),n|m) { rep(i,n) { cin >> e[i]; } text = ""; rep(i,m) { string content; cin >> content; text += content; } int len = text.size(); rep(i,len+1)rep(j,(1<<n))dp[i][j] = false; int ans = 0; rep(i,len) { rep(j,n) { isAble[i][j] = false; int e_len = e[j].size(); if(i+e_len > text.size())continue; if(text[i] != e[j][0])continue; if(text.substr(i,e_len) == e[j]) { isAble[i][j] = true; dp[i+e_len][(1<<j)] = true; } } } rep(cur,len+1) { rep(state,(1<<n)) { if(dp[cur][state] == false)continue; rep(k,n) { if((state>>k) & 1)continue; if(!isAble[cur][k])continue; int e_len = e[k].size(); if(e[k][0] != text[cur])continue; if(text.size() < cur+e_len)continue; //if(text.substr(cur,e_len) == e[k]) <= 毎回これやるとTLE //{ dp[cur+e_len][state|(1<<k)] = true; //} } } if(dp[cur][(1<<n)-1])ans++; } printf("%d\n",ans); } return 0; }