天下一プログラマーコンテスト2014 予選B エターナルスタティックファイナル

問題

B - エターナルスタティックファイナル

文字列Sをn個の文字列Tの組み合わせでつくる場合の場合の数を求める問題です。

考察

Sのi番目までの組み合わせの数をdp[i]とおいて，動的計画法で求めることを考えましたが，遷移式をうまく立てられませんでした。

解説ACです。

学んだこと

範囲for文の書き方

stringを要素にもつ配列Tの各要素tを順番に回す場合　for(const string & t:T)でかけることを学びました。
const string & tのところは，auto tでもよく，その方が簡潔です。

この&がまだよくわかってません。

文字列の比較関数　compare

文字列の操作の関数ではsubstrをよく使いますが，compareを使ったことはありませんでした。
substrを使っても書けそうですが，compareで書いた方が簡潔です。

compareは，s.compare("ABC")といった形で特定の文字列との完全一致を見る使い方と，s.compare(検索開始位置，検索する長さ，検索対象文字列）で位置指定して一致を見る使い方があり，今回は後者を使います。

dp[i]を求める場合，i番目の位置からTの要素tが直前の部分文字列として一致するかどうかを見るので，検索開始位置は，i-t.length()であり，検索する長さはt.length()であり，検索対象文字列はtになります。

なお，dp(0)=1を初期値で入れておくのもポイントだと感じました。

提出コード

#include <bits/stdc++.h>
using namespace std;
static const int MOD=1000000007;
int dp[1100];

int main(){
  int n;
  cin>>n;
  string S;
  cin>>S;
  string T[n];
  for(int i=0;i<n;i++){
    cin>>T[i];
  }
  //int dp[S.length()+1];
  dp[0]=1;
  for(int i=1;i<=S.length();i++){
    for(const string & t:T){
      if(i>=t.length() && S.compare(i-t.length(),t.length(),t)==0){
        dp[i]=(dp[i]+dp[i-t.length()])%MOD;
      }
    }
  }
  cout<<dp[S.length()]<<endl;
  return 0;
}

追記

いつも使っているsubstrでもやってみると簡単に書けました。

#include <bits/stdc++.h>
using namespace std;
static const int MOD=1000000007;
int dp[1100];

int main(){
  int n;
  cin>>n;
  string S;
  cin>>S;
  string T[n];
  for(int i=0;i<n;i++){
    cin>>T[i];
  }
  //int dp[S.length()+1];
  dp[0]=1;
  for(int i=1;i<=S.length();i++){
    for(const string & t:T){
      if(i>=t.length() && S.substr(i-t.length(),t.length())==t){
        dp[i]=(dp[i]+dp[i-t.length()])%MOD;
      }
    }
  }
  cout<<dp[S.length()]<<endl;
  return 0;
}