結果

問題 No.2626 Similar But Different Name
ユーザー AerenAeren
提出日時 2024-02-09 22:54:44
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 290 ms / 3,000 ms
コード長 7,296 bytes
コンパイル時間 3,485 ms
コンパイル使用メモリ 269,868 KB
実行使用メモリ 106,908 KB
最終ジャッジ日時 2024-09-28 16:05:47
合計ジャッジ時間 9,035 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
// #include <x86intrin.h>
using namespace std;
#if __cplusplus >= 202002L
using namespace numbers;
#endif

// z[i]: largest prefix(suffix if Reverse) starting(ending if Reverse) at i that is also a proper prefix(suffix if Reverse)
// O(n)
template<class Char_Type, bool Reverse = false>
vector<int> z_function(vector<Char_Type> s){
	if(Reverse) reverse(s.begin(), s.end());
	int n = (int)s.size();
	vector<int> z(n);
	for(auto i = 1, j = 0; i < n; ++ i){
		if(i < j + z[j]) z[i] = min(j + z[j] - i, z[i - j]);
		while(i + z[i] < n && s[z[i]] == s[i + z[i]]) ++ z[i];
		if(i + z[i] > j + z[j]) j = i;
	}
	if(Reverse) reverse(z.begin(), z.end());
	return z;
}

// Returns the list of positions of pattern in text
// O(n + m)
// Requres z_function
template<class Char_Type>
vector<int> find_all_matchings(const vector<Char_Type> &text, vector<Char_Type> pattern){
	int n = (int)text.size(), m = (int)pattern.size();
	pattern.insert(pattern.end(), text.begin(), text.end());
	auto p = z_function(pattern);
	vector<int> pos;
	for(auto i = m; i < n + m; ++ i) if(p[i] >= m) pos.push_back(i - m);
	return pos;
}

struct fast_fourier_transform_wrapper{
	using CD = complex<double>;
	using CLD = complex<long double>;
	// i \in [2^k, 2^{k+1}) holds w_{2^k+1}^{i-2^k}
	static vector<CD> root;
	static vector<CLD> root_ld;
	static void adjust_root(int n){
		if(root.empty()) root = {1, 1}, root_ld = {1, 1};
		for(auto k = (int)root.size(); k < n; k <<= 1){
			root.resize(n), root_ld.resize(n);
			auto theta = polar(1.0L, acos(-1.0L) / k);
			for(auto i = k; i < k << 1; ++ i) root[i] = root_ld[i] = i & 1 ? root_ld[i >> 1] * theta : root_ld[i >> 1];
		}
	}
	// O(n * log(n))
	static void transform(vector<CD> &p, bool invert = false){
		int n = (int)p.size();
		assert(n && __builtin_popcount(n) == 1);
		for(auto i = 1, j = 0; i < n; ++ i){
			int bit = n >> 1;
			for(; j & bit; bit >>= 1) j ^= bit;
			j ^= bit;
			if(i < j) swap(p[i], p[j]);
		}
		adjust_root(n);
		for(auto len = 1; len < n; len <<= 1) for(auto i = 0; i < n; i += len << 1) for(auto j = 0; j < len; ++ j){
			auto x = (double *)&root[j + len], y = (double *)&p[i + j + len];
			CD z(x[0] * y[0] - x[1] * y[1], x[0] * y[1] + x[1] * y[0]);
			p[len + i + j] = p[i + j] - z, p[i + j] += z;
		}
		if(invert){
			reverse(p.begin() + 1, p.end());
			auto inv_n = 1.0l / n;
			for(auto &x: p) x *= inv_n;
		}
	}
	static vector<CD> buffer1, buffer2;
	// O(n * m)
	template<class T>
	static vector<T> convolute_naive(const vector<T> &p, const vector<T> &q){
		vector<T> res(max((int)p.size() + (int)q.size() - 1, 0));
		for(auto i = 0; i < (int)p.size(); ++ i) for(auto j = 0; j < (int)q.size(); ++ j) res[i + j] += p[i] * q[j];
		return res;
	}
	// Safe for sum(p[i]^2 + q[i]^2) lg2(n) < 9e14
	// O(n * log(n))
	template<class T>
	static vector<T> convolute(const vector<T> &p, const vector<T> &q){
		if(min(p.size(), q.size()) < 60) return convolute_naive(p, q);
		int n = 1 << __lg((int)p.size() + (int)q.size() - 1) + 1;
		buffer1.assign(n, 0);
		for(auto i = 0; i < (int)p.size(); ++ i) buffer1[i].real(p[i]);
		for(auto i = 0; i < (int)q.size(); ++ i) buffer1[i].imag(q[i]);
		transform(buffer1);
		for(auto &x: buffer1) x *= x;
		buffer2.assign(n, 0);
		for(auto i = 0; i < n; ++ i) buffer2[i] = buffer1[i] - conj(buffer1[-i & n - 1]);
		transform(buffer2, true);
		vector<T> res((int)p.size() + (int)q.size() - 1);
		for(auto i = 0; i < (int)res.size(); ++ i) res[i] = is_integral_v<T> ? llround(buffer2[i].imag() / 4) : buffer2[i].imag() / 4;
		return res;
	}
	// O(n * log(n))
	static vector<CD> convolute_complex(const vector<CD> &p, const vector<CD> &q){
		if(min(p.size(), q.size()) < 60) return convolute_naive(p, q);
		int n = 1 << __lg((int)p.size() + (int)q.size() - 1) + 1;
		buffer1 = p, buffer2 = q;
		buffer1.resize(n), buffer2.resize(n);
		transform(buffer1), transform(buffer2);
		for(auto i = 0; i < n; ++ i) buffer1[i] *= buffer2[i];
		transform(buffer1, true);
		return {buffer1.begin(), buffer1.begin() + ((int)p.size() + (int)q.size() - 1)};
	}
	// Safe for 64-bit integer range
	// O(n * log(n))
	template<class T>
	static vector<T> convolute_splitting(const vector<T> &p, const vector<T> &q){
		if(min(p.size(), q.size()) < 80) return convolute_naive(p, q);
		int n = 1 << __lg((int)p.size() + (int)q.size() - 1) + 1;
		const int cut = 32000;
		buffer1.assign(n, 0);
		for(auto i = 0; i < (int)p.size(); ++ i) buffer1[i] = {(int)p[i] / cut, (int)p[i] % cut};
		transform(buffer1);
		buffer2.assign(n, 0);
		for(auto i = 0; i < (int)q.size(); ++ i) buffer2[i] = {(int)q[i] / cut, (int)q[i] % cut};
		transform(buffer2);
		for(auto i = 0; i <= n >> 1; ++ i){
			int j = -i & n - 1;
			if(i == j){
				tie(buffer1[i], buffer2[i]) = pair<CD, CD>{
					(buffer1[i] + conj(buffer1[i])) * buffer2[i] / 2.0,
					(buffer1[i] - conj(buffer1[i])) * buffer2[i] / 2i
				};
			}
			else{
				tie(buffer1[i], buffer2[i], buffer1[j], buffer2[j]) = tuple<CD, CD, CD, CD>{
					(buffer1[i] + conj(buffer1[j])) * buffer2[i] / 2.0,
					(buffer1[i] - conj(buffer1[j])) * buffer2[i] / 2i,
					(buffer1[j] + conj(buffer1[i])) * buffer2[j] / 2.0,
					(buffer1[j] - conj(buffer1[i])) * buffer2[j] / 2i
				};
			}
		}
		transform(buffer1, true);
		transform(buffer2, true);
		vector<T> res((int)p.size() + (int)q.size() - 1);
		for(auto i = 0; i < (int)res.size(); ++ i) res[i] = ((T)llround(buffer1[i].real()) * cut + (T)(llround(buffer1[i].imag()) + llround(buffer2[i].real()))) * cut + (T)llround(buffer2[i].imag());
		return res;
	}
	// Safe for 64-bit integer range
	// O(n * log(n))
	template<class T>
	static vector<T> convolute_splitting_mod(const vector<T> &p, const vector<T> &q){
		if(min(p.size(), q.size()) < 80) return convolute_naive(p, q);
		vector<int> p2(p.begin(), p.end()), q2(q.begin(), q.end());
		p2 = convolute_splitting(p2, q2);
		return {p2.begin(), p2.end()};
	}
};
vector<complex<double>> fast_fourier_transform_wrapper::root;
vector<complex<long double>> fast_fourier_transform_wrapper::root_ld;
vector<complex<double>> fast_fourier_transform_wrapper::buffer1;
vector<complex<double>> fast_fourier_transform_wrapper::buffer2;
 
using fft = fast_fourier_transform_wrapper;

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::badbit | ios::failbit);
	int n, m, k;
	vector<int> s, t, slow, tlow;
	cin >> n >> m >> k;
	for(auto rep = 2; rep; -- rep){
		string temp;
		cin >> temp;
		s.resize(n);
		slow.resize(n);
		for(auto i = 0; i < n; ++ i){
			s[i] = islower(temp[i]) ? temp[i] - 'a' : temp[i] - 'A' + 26;
			slow[i] = islower(temp[i]) ? temp[i] - 'a' : temp[i] - 'A';
		}
		swap(n, m);
		swap(s, t);
		swap(slow, tlow);
	}
	auto match = find_all_matchings(slow, tlow);
	vector<int> p(n), q(m);
	for(auto i = 0; i < n; ++ i){
		p[i] = s[i] < 26;
	}
	for(auto j = 0; j < m; ++ j){
		q[m - 1 - j] = t[j] >= 26;
	}
	vector<int> cnt(n);
	auto pq01 = fft::convolute(p, q);
	for(auto i = 0; i <= n - m; ++ i){
		cnt[i] += pq01[m - 1 + i];
	}
	for(auto &x: p){
		x = !x;
	}
	for(auto &x: q){
		x = !x;
	}
	auto pq10 = fft::convolute(p, q);
	for(auto i = 0; i <= n - m; ++ i){
		cnt[i] += pq10[m - 1 + i];
	}
	int res = 0;
	for(auto i: match){
		res += 1 <= cnt[i] && cnt[i] <= k;
	}
	cout << res << "\n";
	return 0;
}

/*

*/
0