文字列上の動的プランニングアルゴリズム------単一文字列の場合

「A」,「G」,「C」,「T」の4文字のみからなるDNA文字列を考える.長さkの文字列Sが与えられる.長さがちょうどnでSを含まない文字列の個数を計算してください.個数mod 10009の結果を出力します.
まず,条件を満たすすべての文字列を生成するという直感的な解法を考える.文字列の個数は4^nに達する可能性がありますが、これは明らかに通用しません.次に、文字列を生成してからSが含まれているかどうかを判断するよりも、無限検索で末尾に1文字ずつ追加して、最後のk文字がSに等しくないことを確認します.最後のk文字以前の文字は,以降の検索に影響を及ぼさないことが分かった.(後方性がなく、私が書いたダイナミックプランニングの一般的な解法を見ることができる文章が分からない)ので、残りの文字の個数と最後のk-1文字を状態としてダイナミックプランニングを行うことができます.このような状態数は依然として4^(k-1)に達しています.しかし、実際には、その多くの状態を等価と見なすことができ、必要な状態数を大幅に減少させることができる.まず,Sが「ATCG」に等しいことを例に分析する.ダイナミックプランニングのステータスは、文字の個数と最後の3文字です.例えば,最後の3文字が「TTA」の状態と「CCA」の状態を等価と見なすことができる.これは、「A」がSの最初の文字であるため、「TT」または「CC」の2文字は、後でSが現れるかどうかに影響を及ぼさないからである.同様に、「A」で終わる状態では、「A」の前の文字が何であるかは重要ではないことがわかる.このことから分かるように、「*A」(「」は任意の文字を表す)を1つの状態と見なすことができます.「T」で終わる状態はどうでしょうか.「T」は「S」の2番目の文字です.そのため、この文字がSの出現に影響を与えるには、その前の文字が「A」でなければなりません.また、前に分析したように、前の文字が何であるかは影響しません.だから「*AT」を「一つの状態と見なす.そして『T』の前の文字が『A』でなければ、この『T』も無視できる.以上の分析を総合すると、最初の4^3つの状態は、以下の4つの『A』、*AT』、『ATC』にまとめることができ、その他は、生み出された文字列の接尾辞とSの接頭辞が一致する長さを状態としていることが分かる.したがって,状態総数はk個のみである.次に,Sを「ATCATCG」に等しくするより複雑な例を考える.このとき、ちょっと注意が必要なところがあります.簡単に前のように扱うと、「ATCATC」と「**ATC」の2つの状態が得られます.「***ATC」の最初の3文字に何の制限も加えなければ、「ATCATC」で終わる状態と、この2つの状態に属するという奇妙な現象が発生します.しかし、この問題を解決するのも簡単です.最初に‘’を導入したのは,後でSが現れるかどうかに影響を及ぼさないことが知られている文字の代わりに用いられた.「ATCATC」では、次の文字が「G」であればSが得られ、Sの出現に影響を与える.だから「ATCATC」は「***ATC」に属すべきではない.この一般化により,状態は生成された文字列の接尾辞とSの接頭辞が一致する長さであるべきであるが,複数の一致がある場合には,最も長いものを状態として選択すべきであることが分かった.動的プランニングアルゴリズムの部分をより効率的にするために、次のプログラムは、ある状態から文字を追加した状態遷移テーブルを予め処理し、それを利用して動的プランニングを完了する.前処理部の複雑さはO(k^3)であり,動的計画の複雑さはO(kn)である.

/*
     
    'A','G','C','T'        DNA   。        k     S。
         n     S       。     mod 10009     
*/
#include
#include
#include
using namespace std;
const char *AGCT = "AGCT";
const int MOD = 10009;
const int MAX_K = 105;
const int MAX_N = 10005;

//  
int N,K;
string S;
int next[MAX_K][4];//              
int dp[MAX_N + 1][MAX_K];

void solve(){
    //   
    for(int i=0;ifor(int j=0;j<4;j++){
            //  S    i          
            string s = S.substr(0,i) + AGCT[j];
            //         ，     S   
            while(S.substr(0,s.length()) != s){
                s = s.substr(1);
            } 
            next[i][j] = s.length(); 
        } 
    } 

    //         
    dp[0][0] = 1;
    for(int i=1;i0][i] = 0;
    //    
    for(int t=0;tfor(int i=0;i1][i] = 0;
        for(int i=0;ifor(int j=0;j<4;j++){
                int ti = next[i][j];
                if(ti == K)
                    continue;//      S
                dp[t+1][ti] = (dp[t+1][ti] + dp[t][i]) % MOD; 
            } 
        } 
    } 

    int ans = 0;
    for(int i=0;iprintf("%d
",ans); 
} 
int main(){
    cin>>N>>K;
    cin>>S;
    solve(); 
    return 0;
}