久々の難易度8。
https://leetcode.com/contest/weekly-contest-182/problems/find-all-good-strings/
問題
正整数Nと、N文字の文字列s1,s2、あと別の文字列evilが与えられる。
N文字のアルファベット小文字の文字列のうち、辞書順でs1以上s2以下でevilを部分文字列に含まないものは何通りか。
解法
evilに対しKMP法のテーブルを作っておけば、状態として
(N文字中prefixを何文字定めたか, s1より大きいことが確定したか, s2より小さいことが確定したか, テーブル上の位置)
を持ってあとは桁DPと似た要領で上の文字から総当たりしていくだけ。
int stt[52][26]; const char base='a'; void CreateSTT(string& pat) { int x,y,z,l; ZERO(stt); l=pat.size(); FOR(x,l) { FOR(y,26) { if(base+y == pat[x]) stt[x][y]=x+1; else { string pre=pat.substr(0,x)+(char)(base+y); for(z=1;z<=x;z++) if(pre.substr(pre.size()-z) == pat.substr(0,z)) stt[x][y]=z; } } } FOR(y,26) stt[l][y]=l; } int N; ll dp[505][52][2][2]; const ll mod=1000000007; string S1,S2,E; class Solution { public: ll hoge(int cur,int ev,int mo,int le) { if(cur==N) return (ev<E.size()); ll& ret=dp[cur][ev][mo][le]; if(ret>=0) return ret; ret=0; int i; FOR(i,26) { if(mo==0 && i<S1[cur]-'a') continue; if(le==0 && i>S2[cur]-'a') continue; int nmo=mo | (i>S1[cur]-'a'); int nle=le | (i<S2[cur]-'a'); int nev=stt[ev][i]; ret+=hoge(cur+1,nev,nmo,nle); } ret%=mod; return ret; } int findGoodStrings(int n, string s1, string s2, string evil) { MINUS(dp); CreateSTT(evil); S1=s1; S2=s2; E=evil; N=n; return hoge(0,0,0,0); } };
まとめ
なんで出題までに問題No確定させてくれないの…?