読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

AOJ 1291 : Search of Concatenated Strings

AOJ 動的計画法

問題リンク: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;
}