yukicoder : No.2172 SEARCH in the Text Editor

これは割とすぐわかった。
https://yukicoder.me/problems/no/2172

問題

N要素の文字列列Sが与えられる。
各S[i]は以下のいずれかの形式で与えられる。

• 文字列が直接与えられる。
• iより小さいindex2つj,kが指定される。S[i]=S[j]+S[k]とする。

文字列Tが与えられる。
S[N]にTは部分文字列として何回登場するか。

解法

KMP法の要領で、Tに対応する状態遷移図を考える。
状態遷移図の各位置にいる状態で、各S[i]による状態遷移をしたときの行先とTのマッチング回数をそれぞれ求めて行こう。

int N,L;
string T,S[101010];
ll nex[101010][55];
ll num[101010][55];

int stt[1024][257];
const ll mo=998244353;
const char base='\0';
void CreateSTT(string& pat) {
	int x,y,z,l;
	ZERO(stt);
	l=pat.size();
	FOR(x,l+1) {
		FOR(y,256) {
			string pre=pat.substr(0,x)+(char)(base+y);
			for(z=1;z<=min(pat.size(),pre.size());z++) if(pre.substr(pre.size()-z) == pat.substr(0,z)) stt[x][y]=z;
		}
		if(x!=l) stt[x][y]=x+1;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>T;
	L=T.size();
	CreateSTT(T);
	
	FOR(i,N) {
		cin>>s;
		if(s=="~") {
			cin>>x>>y;
			x--,y--;
			FOR(j,L+1) {
				nex[i][j]=nex[y][nex[x][j]];
				num[i][j]=(num[x][j]+num[y][nex[x][j]])%mo;
			}
		}
		else {
			FOR(j,L+1) {
				nex[i][j]=j;
				FORR(c,s) {
					nex[i][j]=stt[nex[i][j]][c];
					if(nex[i][j]==L) num[i][j]++;
				}
			}
		}
	}
	
	cout<<num[N-1][0]<<endl;
	
}

まとめ

★3でも簡単な時と難しいときがあるな。