54 D Writing a Song

問題

長さnの歌を次の条件を満たすように作りたい。
文字列でPが与えられる。

• そのPが、指定された位置には出現し、指定されていない位置には出現しない。
• アルファベットの最初からk種類（以下）のみからなる

出現の指定は01からなる文字列により行われる。
i番目が0ならば、歌のi文字目からはPではない文字列が始まり、
1ならばPが始まる。

制約条件

n,m≦100
k≦26

方針

PMA(パターンマッチオートマトン)を作る。

すると、dp[pos][state]を、
歌をpos文字作って、そのときのオートマトンの状態がstateであるような状態にたどりつけるかどうかとするDPが出来る。

DPの経路復元をしてやることにより歌が出力できる。

ソースコード

int *buildFail(char *p) {
  int m = strlen(p);
  int *fail = new int[m+1];
  int j = fail[0] = -1;
  for (int i = 1; i <= m; ++i) {
    while (j >= 0 && p[j] != p[i-1]) j = fail[j];
    fail[i] = ++j;
  }
  return fail;
}
int n,k, *pma;
char in[101],oc[101];
int prev[101][101],c[101][101];
bool dp[101][101];

void run(){
  cin>>n>>k;
  cin>>in>>oc;
  pma=buildFail(in);
  
  memset(dp,0,sizeof(dp)); dp[0][0]=1;
  int m=strlen(in),l=strlen(oc);
  rep(i,n)rep(j,m)if(dp[i][j]){
    rep(p,k){
      int s=j;
      while(s>=0&&in[s]-'a'!=p)s=pma[s];
      if(++s>=m){
        s=pma[s];
        if(i+1<m||oc[i-m+1]=='1'){
          dp[i+1][s]=1;
          c[i+1][s]=p; prev[i+1][s]=j;
        }
      }
      else{
        if(i+1<m||oc[i-m+1]=='0'){
          dp[i+1][s]=1;
          c[i+1][s]=p; prev[i+1][s]=j;
        }
      }
    }
  }
  rep(i,m+1)if(dp[n][i]){
    string ans;
    for(int s=i,j=n;j;j--)ans.pb(c[j][s]+'a'), s=prev[j][s];
    reverse(all(ans));
    cout<<ans<<endl; return;
  }
  cout<<"No solution"<<endl;
}