#1179209 (C++23) No.3638 Itsuki

• 問題: No.3638 Itsuki
• ユーザー: kwm_t
• 提出日時: 2026-08-25 21:40:37
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 48 ms / 3,000 ms
• コード長: 3,270 bytes
• コンパイル時間: 2,628 ms
• コンパイル使用メモリ: 336,312 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2026-08-25 21:40:48
• 合計ジャッジ時間: 4,732 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

サブタスク	配点	結果
サンプル	0 %	AC * 2
小課題1	10 %	AC * 5
小課題2	50 %	AC * 6
小課題3	40 %	AC * 18
合計	100 点

ソースコード

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
// using namespace atcoder;
// using mint = modint1000000007;
// const int mod = 1000000007;
// using mint = modint998244353;
// const int mod = 998244353;
// const int INF = 1e9;
// const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rrep(i, n) for (int i = (n)-1; i >= 0; --i)
#define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define P pair<int, int>
template<typename A, typename B> inline bool chmax(A& a, const B& b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A& a, const B& b) { if (a > b) { a = b; return true; } return false; }
#ifndef KWM_T_STRING_KMP_HPP
#define KWM_T_STRING_KMP_HPP

#include <vector>

/**
 * @brief KMP (Knuth-Morris-Pratt) 法（最適化版）
 *
 * パターン列の prefix function（failure function）を構築し、
 * テキスト中の出現位置を高速に列挙する。
 * 本実装は next 配列の最適化を含む。
 *
 * 典型用途:
 *   - 文字列検索（完全一致）
 *   - 部分文字列の出現位置列挙
 *
 * 計算量:
 *   - 構築: O(|pattern|)
 *   - 検索: O(|text|)
 *
 * @tparam T
 *   - size(), operator[] を持ち、== で比較可能なコンテナ
 *   - 例: std::string, std::vector<int>
 *
 * @param pattern 検索したいパターン
 *
 * 制約 / 注意:
 *   - pattern は空でないことを想定
 *
 * 使用例:
 *   kwm_t::string::KMP<std::string> kmp("aba");
 *   auto res = kmp.search("ababa");
 *   // res = {0, 2}
 *
 * verified:
 *   - https://atcoder.jp/contests/awc0045/submissions/74809117
 */
namespace kwm_t::string {

template <typename T>
class KMP {
public:
	explicit KMP(const T& pattern) : pattern(pattern) {
		build();
	}

	// text 内の一致開始位置をすべて返す
	std::vector<int> search(const T& text) const {
		std::vector<int> res;
		int j = 0;
		for (int i = 0; i < (int)text.size(); ++i) {
			while (j != -1 && pattern[j] != text[i]) j = next[j];
			++j;
			if (j == n) {
				res.push_back(i - j + 1);
				j = next[j];
			}
		}
		return res;
	}

	// failure function を取得（デバッグ・応用用）
	const std::vector<int>& get_next() const {
		return next;
	}

private:
	int n;
	T pattern;
	std::vector<int> next;

	void build() {
		n = (int)pattern.size();
		next.assign(n + 1, 0);

		next[0] = -1;
		int j = -1;

		for (int i = 0; i < n; ++i) {
			while (j != -1 && pattern[j] != pattern[i]) j = next[j];
			++j;
			if (i + 1 < n && pattern[i + 1] == pattern[j]) {
				next[i + 1] = next[j]; // 最適化
			}
			else {
				next[i + 1] = j;
			}
		}
	}
};

} // namespace kwm_t::string

#endif // KWM_T_STRING_KMP_HPP
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n, q; cin >> n >> q;
	string s; cin >> s;
	while (q--) {
		int t; cin >> t;
		if (t == 1) {
			int i; char c; cin >> i >> c;
			s[i - 1] = c;
		}
		else {
			string t; cin >> t;
			kwm_t::string::KMP kmp(t);
			auto a = kmp.search(s);
			if (a.size() == 0)cout << "No" << endl;
			else cout << "Yes" << endl;
		}
	}
	return 0;
}