文字列　蟻 #C++

禁止文字列
A,G,C,Tの4種類の文字のみが含まれるDNAの文字列を考える。k文字の文字列Sが与えられる。ちょうどn文字であって文字列Sを含まない文字列の個数を　mod 10009で答えよ

方針　文字列の動的計画法
S="AT"の時を考える
末尾がAで終わる状態に関してはそれより前の文字に関心を持つ必要がない。したがってそれらをまとめてAという一つの状態としてよい。末尾がTで終わるときは*ATという状態が考えられる。以上のように考えると以下の4つの状態にまとめられる。A,*AT,ATC,それ以外
つまり、生成している文字列の末尾がSの先頭何文字に一致しているか、を状態にすることにより状態をk個にできる
一般的に考えると、状態は、生成している文字列の末尾がSの先頭何文字に一致しているか、ただし一致のさせ方が複数通りある場合は最長の場合とすればよい


int N, K;
string S;
const char *AGCT = "AGCT";
const int MOD = 10009;
int nex[110][4];//  1文字加えた際に移動する先の状態
int dp[10010][101];
//dp[i][j]:=作成しているDNA文字列がi文字であってその末尾がSの先頭j文字と一致している状態の総数
void solve() {
    for (int i = 0; i < K; ++i) {
        for (int j = 0; j < 4; ++j) {
            //一致しているi文字に1文字加えた文字列
            string s = S.substr(0, i) + AGCT[j];
            //Sの先頭に一致するまで先頭から1文字削る
            while (S.substr(0, s.length()) != s) {
                s = s.substr(1);
            }
            nex[i][j] = s.length();
        }
    }
}
int main() {
    cin >> N >> K;
    cin >> S;
    solve();
    dp[0][0] = 1;
    for (int i = 1; i < K; ++i) {
        dp[0][i] = 0;
    }
    for (int t = 0; t < N; ++t) {
        for (int i = 0; i < K; ++i) {
            for (int j = 0; j < 4; ++j) {
                int ti = nex[i][j];
                if (ti == K)continue;
                dp[t + 1][ti] = (dp[t + 1][ti] + dp[t][i]) % MOD;
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < K; ++i) {
        ans = (ans + dp[N][i]) % MOD;
    }
    cout << ans << endl;
    return 0;
}

複数文字列の場合
A,G,C,Tの4種類の文字のみが含まれるDNAの文字列を考えます。元となる文字列Sと禁止パターンとしてn個の文字列P1,P2,,,Pnが与えられます。文字列Sを変更して、禁止パターンがまったく含まれないような文字列にしたいです。変更として許される操作はある場所の文字を別の文字に変更すること。不可能なら-1を、可能なら変更の最小回数を答えよ

const string DNA = "AGCT";
int nex[1010][4];
int dp[1010][1010];//dp[i][j]:=Sをi文字目まで見た時そのsuffixがj番目の状態と一致している
//ようにするために必要な操作の最小値
int main() {
    string s;
    int n, case_num = 0;
    while (cin >> n) {
        case_num++;
        string p[1010];
        REP(i, n)cin >> p[i];
        cin >> s;
        vector<string>pfx;
        for (int i = 0; i < n; ++i) {
            int len = p[i].size();
            for (int k = 0; k <= len; ++k) {
                pfx.push_back(p[i].substr(0, k));
            }
        }
        //重複要素を取り除く
        sort(pfx.begin(), pfx.end());
        pfx.erase(unique(pfx.begin(), pfx.end()), pfx.end());
        int M = pfx.size();
        vector<int>ng_state(M, false);
        for (int i = 0; i < M; ++i) {
            for (int k = 0; k < n; ++k) {
                //元のパターンと一致するようなprefixがあれば遷移不可
                int lenA = p[k].length(), lenB = pfx[i].length();
                if (lenA <= lenB) {
                    if (pfx[i].substr(lenB - lenA, lenA) == p[k]) {
                        ng_state[i] = true;
                    }
                }
            }
            //1文字足してどの状態に行くか判定
            for (int c = 0; c < 4; ++c) {
                string str = pfx[i] + DNA[c]; int k;
                while (1) {
                    k = lower_bound(pfx.begin(), pfx.end(), str) - pfx.begin();
                    if (k < M&&pfx[k] == str)break;
                    str = str.substr(1);
                }
                nex[i][c] = k;
            }
        }
        int L = s.length();
        fill(dp[0], dp[1010], INF);
        dp[0][0] = 0;
        for (int i = 0; i < L; ++i) {
            for (int j = 0; j < M; ++j) {
                for (int c = 0; c < 4; ++c) {
                    int nj = nex[j][c];
                    if (ng_state[j] || ng_state[n])continue;
                    int cost = (s[i] != DNA[c]);
                    dp[i + 1][nj] = min(dp[i + 1][nj], dp[i][j] + cost);
                }
            }
        }
        int ans = INF;
        for (int i = 0; i < M; ++i)if (ng_state[i] == false)ans = min(ans, dp[L][i]);
        cout << "Case " << case_num << ": " << (ans == INF ? -1 : ans) << endl;
    }
    return 0;
}

文字列検索
文字列Sに含まれる文字列Tの場所を探したり含む回数を数えたりすることを文字列検索と呼ぶ。以下、Sの長さをn,Tの長さをmとする。ナイーブにはSでの開始位置を全て試し一致しているかどうか調べるという方法があるがより効率的に行うことができるアルゴリズムがいくつか存在する。ハッシュを用いた方法を書く。各開始位置に対し、そこからの文字列が一致しているかどうかを文字列比較によりO(m)かけて調べる代わりにそこからm文字の部分文字列のハッシュ値が文字列Tのハッシュ値一致するかを比較することによりo(1)で調べる。

文字列 蟻

文字列　蟻