P4591 [TJOI2018] 碱基序列，详细题解 – Emoji-happy

「文字列ハッシュ + dp」の良い質問

1. タイトルの簡単な説明

質問は少し理解するのが難しいです。翻訳してください。
DNA 文字列が与えられると \(s\) そして \(k\) グループ文字列、各グループから文字列を 1 つだけ選択しますグループ順に接合されます。必要なスプライシング結果は次のとおりです。 \(s\) の部分文字列、内のすべての代替を検索します \(s\) 出現回数の合計（同じ解が複数箇所に出現する場合は別々にカウントします）。
答えは正しいです \(10^9+7\) 型を取ります。
データ範囲: \(1\le k\le 100,1\le |s|\le 10000,1\le a_i\le 10\)

2. アイデア

これは文字列間の一致であり、データ範囲が小さくないため、「文字列ハッシュ」方法を使用することを選択します。 \(O(1)\) 効率的な判断。
見つけるのは難しくありません。最初の処理を行うとき \（私\） 塩基配列を組み立てるとき、その答えへの寄与は次のとおりです。 \(i-1\) グループ塩基配列が転送されます。dp を考慮してください。

1. ステータスの定義

私たちが定義する \(dp[i][r]\) 処理が完了したことを示します \（私\） 塩基配列を組み立てた後、スプライシング結果は正確に終了します。 \(s\) の \(r\) 拠点のプラン数

• \（私\） 処理されたグループの数を示します
• \(r\) 急行最後の文字は現在 \(s\) の場所 \((1\SIM のみ)\)
• 意味：前に \（私\） 選択した文字列を隣接して連結した後、最後の文字が続きます。 \(s)[r]\)

2.初期化

for(int i=0;i<=10000;i++)dp[0][i]=1;

dp[0][r]=1意味: 文字列が選択されていない場合は、s 以降の任意の位置から開始できます。
初期化がない場合、最初の段落は s の先頭からのみ一致し、結果は次のようになります。プレフィックスマッチングそれよりもどこにでもマッチ

3. 転送

for(int l=1,r=lx;l<=len and r<=len;r++,l++){
	int key=(hs[r]+mod-hs[l-1]*mi[r-l+1]%mod)%mod;
	if (key!=tar)continue;
	dp[i][r]+=dp[i-1][l-1];
	dp[i][r]%=mod;
}

核となるアイデアはスプライシング：

• フォワード i-1 グループが集まったら、最後のキャラクターが登場します s[l-1]
• いいえ。 i 選択した文字列をグループ化する x 全く等しい s[l...r]
• それから前に i グループが集まった後、 s[r]

4. 回答統計

for(int i=1;i<=len;i++){
	ans+=dp[k][i]%mod;
}

基本シーケンスの k 個のグループすべてを処理した後、s の各位置で終了する解の数を合計します。忘れずに修正してください \(10^9+7\) 型を取る

3. コードを実装する

質問ポータル
これが紫色の質問になるとは思いませんでした

#include 
using namespace std;
#define int unsigned long long
const int mod=1e9+7;
const int N=1e4+5;
int k,hs[N],mi[N],dp[105][N],ans;
string s;
signed main(){
	for(int i=0;i<=10000;i++)dp[0][i]=1;
	mi[0]=1;
	cin>>k>>s;
	int len=s.size();
	s=" "+s;
	for(int i=1;i<=len;i++){
		mi[i]=mi[i-1]*127%mod;
		hs[i]=(hs[i-1]*127+s[i])%mod;
	}
	for(int i=1;i<=k;i++){
		int a;
		cin>>a;
		for(int j=1;j<=a;j++){
			string x;
			cin>>x;
			int tar=0,lx=x.size();
			x=" "+x;
			for(int u=1;u<=lx;u++){
				tar=(tar*127+x[u])%mod;
			}
			for(int l=1,r=lx;l<=len and r<=len;r++,l++){
				int key=(hs[r]+mod-hs[l-1]*mi[r-l+1]%mod)%mod;
				if (key!=tar)continue;
				dp[i][r]+=dp[i-1][l-1];
				dp[i][r]%=mod;
			}
		}
	}
	for(int i=1;i<=len;i++){
		ans+=dp[k][i]%mod;
	}
	cout<