結果

問題 No.3638 Itsuki
コンテスト
ユーザー amesyu
提出日時 2026-08-25 14:27:20
言語 C++23
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 306 ms / 3,000 ms
+ 118µs
コード長 1,610 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,375 ms
コンパイル使用メモリ 335,696 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2026-08-25 14:27:25
合計ジャッジ時間 4,823 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge3_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
サンプル 0 % AC * 2
小課題1 10 % AC * 5
小課題2 50 % AC * 6
小課題3 40 % AC * 18
合計 100 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

struct RollingHash {
public:
    static const long long B1 = 10007;
    static const long long B2 = 10009;
    static const long long MOD = 1000000007;
    vector<long long> hash1, hash2, pow1, pow2;
    RollingHash() : RollingHash("") {}
    RollingHash(const string& s) : n_(s.size()), hash1(s.size() + 1), hash2(s.size() + 1), pow1(s.size() + 1), pow2(s.size() + 1) {
        hash1[0] = hash2[0] = 0;
        pow1[0] = pow2[0] = 1;
        for (int i = 0; i < (int)s.size(); i++) {
            hash1[i + 1] = (hash1[i] * B1 + s[i]) % MOD;
            hash2[i + 1] = (hash2[i] * B2 + s[i]) % MOD;
            pow1[i + 1] = pow1[i] * B1 % MOD;
            pow2[i + 1] = pow2[i] * B2 % MOD;
        }
    }
    long long get(int l, int r) const {
        long long res1 = (hash1[r] - hash1[l] * pow1[r - l]) % MOD;
        if (res1 < 0) res1 += MOD;
        long long res2 = (hash2[r] - hash2[l] * pow2[r - l]) % MOD;
        if (res2 < 0) res2 += MOD;
        return res1 * MOD + res2;
    }
private:
    int n_;
    
};

int main() {
	// 毎回ロリハ更新すれば
	// O(NQ)
	int n, q; cin >> n >> q;
	string s; cin >> s;
	
	while (q--) {
		int t; cin >> t;
		if (t == 1) {
			int i; cin >> i; --i;
			char c; cin >> c;
			s[i] = c;
		} else {
			string t; cin >> t;
			RollingHash rs(s);
			RollingHash rt(t);
			int m = t.size();
			bool ok = false;
			long long hash_t = rt.get(0, m);
			for (int i = 0; i < n - m + 1; ++i) {
				long long hash = rs.get(i, i + m);
				if (hash == hash_t) ok = true;
			}
			cout << (ok ? "Yes" : "No") << endl;
		}
	}
}
0