https://atcoder.jp/contests/past202004-open/tasks/past202004_d
解説
https://atcoder.jp/contests/past202004-open/submissions/12895517
競技プログラミングの基本は全探索である。
文字列Tは全部で273+272+27通りある。
これはだいたい20000通りくらいであり、一般に105くらいまでは全探索余裕なので、これは全探索できる。
なので、文字列Tの全探索が必要となる。
基本的には重複順列の全列挙と同じなので、dfsが典型としてよく使われるので、dfsを使うといい。
他にもキューでBFSをしたり、色々な方法がある。
すべてのTが全列挙できたら、あとは、Sにマッチするものをカウントすればいい。
check(S, T) := TがSにマッチするか
これもSの先頭からTに合うかどうかマッチングを試していく。
Tが.であればチェックをスキップして、そうでないなら、SとTが合うかどうかをチェックしていく。
string S; //--------------------------------------------------------------------------------------------------- bool check(string s, string t) { int ns = s.length(); int nt = t.length(); rep(i, 0, ns - nt + 1) { bool ok = true; rep(j, 0, nt) { if (t[j] == '.') continue; if (s[i + j] != t[j]) ok = false; } if (ok) return true; } return false; } //--------------------------------------------------------------------------------------------------- vector<string> Ts; void dfs(int cu, string s) { if (0 < cu) Ts.push_back(s); if (cu == 3) return; rep(i, 0, 26) dfs(cu + 1, s + char('a' + i)); dfs(cu + 1, s + "."); } //--------------------------------------------------------------------------------------------------- void _main() { cin >> S; dfs(0, ""); int ans = 0; fore(T, Ts) if (check(S, T)) ans++; cout << ans << endl; }