結果
| 問題 | No.2626 Similar But Different Name |
| ユーザー |
 ruthen71
|
| 提出日時 | 2024-02-10 00:36:14 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 392 ms / 3,000 ms |
| コード長 | 16,088 bytes |
| コンパイル時間 | 3,181 ms |
| コンパイル使用メモリ | 185,876 KB |
| 実行使用メモリ | 67,184 KB |
| 最終ジャッジ日時 | 2024-09-28 16:46:53 |
| 合計ジャッジ時間 | 10,669 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,820 KB |
| testcase_01 | AC | 2 ms
6,816 KB |
| testcase_02 | AC | 2 ms
6,816 KB |
| testcase_03 | AC | 2 ms
6,820 KB |
| testcase_04 | AC | 2 ms
6,816 KB |
| testcase_05 | AC | 2 ms
6,816 KB |
| testcase_06 | AC | 2 ms
6,820 KB |
| testcase_07 | AC | 2 ms
6,816 KB |
| testcase_08 | AC | 2 ms
6,820 KB |
| testcase_09 | AC | 2 ms
6,820 KB |
| testcase_10 | AC | 3 ms
6,820 KB |
| testcase_11 | AC | 4 ms
6,816 KB |
| testcase_12 | AC | 3 ms
6,816 KB |
| testcase_13 | AC | 4 ms
6,816 KB |
| testcase_14 | AC | 4 ms
6,820 KB |
| testcase_15 | AC | 4 ms
6,820 KB |
| testcase_16 | AC | 4 ms
6,816 KB |
| testcase_17 | AC | 4 ms
6,820 KB |
| testcase_18 | AC | 389 ms
67,088 KB |
| testcase_19 | AC | 65 ms
31,268 KB |
| testcase_20 | AC | 64 ms
31,236 KB |
| testcase_21 | AC | 69 ms
31,184 KB |
| testcase_22 | AC | 376 ms
52,476 KB |
| testcase_23 | AC | 379 ms
52,720 KB |
| testcase_24 | AC | 375 ms
49,332 KB |
| testcase_25 | AC | 374 ms
50,428 KB |
| testcase_26 | AC | 370 ms
52,816 KB |
| testcase_27 | AC | 372 ms
53,304 KB |
| testcase_28 | AC | 371 ms
51,248 KB |
| testcase_29 | AC | 374 ms
49,024 KB |
| testcase_30 | AC | 377 ms
50,368 KB |
| testcase_31 | AC | 368 ms
52,024 KB |
| testcase_32 | AC | 373 ms
53,032 KB |
| testcase_33 | AC | 373 ms
53,036 KB |
| testcase_34 | AC | 369 ms
49,120 KB |
| testcase_35 | AC | 372 ms
52,252 KB |
| testcase_36 | AC | 361 ms
49,084 KB |
| testcase_37 | AC | 392 ms
67,184 KB |
ソースコード
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <deque>
#include <forward_list>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#ifdef RUTHEN_LOCAL
#include <debug.hpp>
#else
#define show(x) true
#endif
// type definition
using i64 = long long;
using i128 = __int128_t;
using u32 = unsigned int;
using u64 = unsigned long long;
using u128 = __uint128_t;
using f32 = float;
using f64 = double;
using f128 = long double;
template <class T> using pque = std::priority_queue<T>;
template <class T> using pqueg = std::priority_queue<T, std::vector<T>, std::greater<T>>;
#define overload4(_1, _2, _3, _4, name, ...) name
#define overload3(_1, _2, _3, name, ...) name
#define overload2(_1, _2, name, ...) name
// loop
#define REP1(a) for (long long _ = 0; _ < (a); _++)
#define REP2(i, a) for (long long i = 0; i < (a); i++)
#define REP3(i, a, b) for (long long i = (a); i < (b); i++)
#define REP4(i, a, b, c) for (long long i = (a); i < (b); i += (c))
#define REP(...) overload4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__)
#define RREP1(a) for (long long _ = (a)-1; _ >= 0; _--)
#define RREP2(i, a) for (long long i = (a)-1; i >= 0; i--)
#define RREP3(i, a, b) for (long long i = (b)-1; i >= (a); i--)
#define RREP(...) overload3(__VA_ARGS__, RREP3, RREP2, RREP1)(__VA_ARGS__)
#define FORE1(x, a) for (auto&& x : a)
#define FORE2(x, y, a) for (auto&& [x, y] : a)
#define FORE3(x, y, z, a) for (auto&& [x, y, z] : a)
#define FORE(...) overload4(__VA_ARGS__, FORE3, FORE2, FORE1)(__VA_ARGS__)
#define FORSUB(t, s) for (long long t = (s); t; t = (t - 1) & (s))
// function
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(a) std::sort((a).begin(), (a).end())
#define RSORT(a) std::sort((a).rbegin(), (a).rend())
#define REV(a) std::reverse((a).begin(), (a).end())
#define UNIQUE(a) \
std::sort((a).begin(), (a).end()); \
(a).erase(std::unique((a).begin(), (a).end()), (a).end())
#define LEN(a) int((a).size())
#define MIN(a) *std::min_element((a).begin(), (a).end())
#define MAX(a) *std::max_element((a).begin(), (a).end())
#define SUM1(a) std::accumulate((a).begin(), (a).end(), 0LL)
#define SUM2(a, x) std::accumulate((a).begin(), (a).end(), (x))
#define SUM(...) overload2(__VA_ARGS__, SUM2, SUM1)(__VA_ARGS__)
#define LB(a, x) std::distance((a).begin(), std::lower_bound((a).begin(), (a).end(), (x)))
#define UB(a, x) std::distance((a).begin(), std::upper_bound((a).begin(), (a).end(), (x)))
template <class T, class U> inline bool chmin(T& a, const U& b) { return (a > T(b) ? a = b, 1 : 0); }
template <class T, class U> inline bool chmax(T& a, const U& b) { return (a < T(b) ? a = b, 1 : 0); }
template <class T, class S> inline T floor(const T x, const S y) {
assert(y);
return (y < 0 ? floor(-x, -y) : (x > 0 ? x / y : x / y - (x % y == 0 ? 0 : 1)));
}
template <class T, class S> inline T ceil(const T x, const S y) {
assert(y);
return (y < 0 ? ceil(-x, -y) : (x > 0 ? (x + y - 1) / y : x / y));
}
template <class T, class S> std::pair<T, T> inline divmod(const T x, const S y) {
T q = floor(x, y);
return {q, x - q * y};
}
// bit operation
// (0, 1, 2, 3, 4) -> (0, 1, 1, 2, 1)
int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(i64 x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(i64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(i64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
// binary search
template <class T, class F> T bin_search(T ok, T ng, F& f) {
while ((ok > ng ? ok - ng : ng - ok) > 1) {
T md = (ng + ok) >> 1;
(f(md) ? ok : ng) = md;
}
return ok;
}
template <class T, class F> T bin_search_real(T ok, T ng, F& f, const int iter = 100) {
for (int _ = 0; _ < iter; _++) {
T md = (ng + ok) / 2;
(f(md) ? ok : ng) = md;
}
return ok;
}
// rotate matrix counterclockwise by pi / 2
template <class T> void rot(std::vector<std::vector<T>>& a) {
if (int(a.size()) == 0) return;
if (int(a[0].size()) == 0) return;
int n = int(a.size()), m = int(a[0].size());
std::vector res(m, std::vector<T>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
res[m - 1 - j][i] = a[i][j];
}
}
a.swap(res);
}
// const value
constexpr int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
// infinity
template <class T> constexpr T INF = 0;
template <> constexpr int INF<int> = 1'000'000'000; // 1e9
template <> constexpr i64 INF<i64> = i64(INF<int>) * INF<int> * 2; // 2e18
template <> constexpr i128 INF<i128> = i128(INF<i64>) * INF<i64>; // 4e36
template <> constexpr u32 INF<u32> = INF<int>; // 1e9
template <> constexpr u64 INF<u64> = INF<i64>; // 2e18
template <> constexpr u128 INF<u128> = INF<i128>; // 4e36
template <> constexpr f32 INF<f32> = INF<i64>; // 2e18
template <> constexpr f64 INF<f64> = INF<i64>; // 2e18
template <> constexpr f128 INF<f128> = INF<i64>; // 2e18
// input
std::istream& operator>>(std::istream& is, __int128_t& x) {
std::string s;
is >> s;
x = 0;
int i = s[0] == '-' ? 1 : 0;
while (i < (int)(s.size())) x = 10 * x + s[i++] - '0';
if (s[0] == '-') x = -x;
return is;
}
std::istream& operator>>(std::istream& is, __uint128_t& x) {
std::string s;
is >> s;
assert(s[0] != '-');
x = 0;
int i = 0;
while (i < (int)(s.size())) x = 10 * x + s[i++] - '0';
return is;
}
template <class T> std::istream& operator>>(std::istream& is, std::vector<T>& v) {
for (auto&& i : v) is >> i;
return is;
}
template <class... T> void in(T&... a) { (std::cin >> ... >> a); }
void scan() {}
template <class Head, class... Tail> void scan(Head& head, Tail&... tail) {
in(head);
scan(tail...);
}
// definition & input
#define INT(...) \
int __VA_ARGS__; \
scan(__VA_ARGS__)
#define I64(...) \
i64 __VA_ARGS__; \
scan(__VA_ARGS__)
#define I128(...) \
i128 __VA_ARGS__; \
scan(__VA_ARGS__)
#define U32(...) \
u32 __VA_ARGS__; \
scan(__VA_ARGS__)
#define U64(...) \
u64 __VA_ARGS__; \
scan(__VA_ARGS__)
#define U128(...) \
u128 __VA_ARGS__; \
scan(__VA_ARGS__)
#define F32(...) \
f32 __VA_ARGS__; \
scan(__VA_ARGS__)
#define F64(...) \
f64 __VA_ARGS__; \
scan(__VA_ARGS__)
#define F128(...) \
f128 __VA_ARGS__; \
scan(__VA_ARGS__)
#define STR(...) \
std::string __VA_ARGS__; \
scan(__VA_ARGS__)
#define CHR(...) \
char __VA_ARGS__; \
scan(__VA_ARGS__)
#define VEC(type, name, size) \
std::vector<type> name(size); \
scan(name)
#define VEC2(type, name1, name2, size) \
std::vector<type> name1(size), name2(size); \
for (int i = 0; i < size; i++) scan(name1[i], name2[i])
#define VEC3(type, name1, name2, name3, size) \
std::vector<type> name1(size), name2(size), name3(size); \
for (int i = 0; i < size; i++) scan(name1[i], name2[i], name3[i])
#define VEC4(type, name1, name2, name3, name4, size) \
std::vector<type> name1(size), name2(size), name3(size), name4(size); \
for (int i = 0; i < size; i++) scan(name1[i], name2[i], name3[i], name4[i])
#define VV(type, name, h, w) \
std::vector name((h), std::vector<type>((w))); \
scan(name)
// output
std::ostream& operator<<(std::ostream& os, const __int128_t& x) {
if (x == 0) {
return os << 0;
}
__int128_t y = (x > 0 ? x : -x);
std::string res;
while (y) {
res += y % 10 + '0';
y /= 10;
}
if (x < 0) res += '-';
std::reverse(res.begin(), res.end());
return os << res;
}
std::ostream& operator<<(std::ostream& os, const __uint128_t& x) {
if (x == 0) {
return os << 0;
}
__uint128_t y = x;
std::string res;
while (y) {
res += y % 10 + '0';
y /= 10;
}
std::reverse(res.begin(), res.end());
return os << res;
}
template <class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
auto n = v.size();
for (size_t i = 0; i < n; i++) {
if (i) os << ' ';
os << v[i];
}
return os;
}
template <class... T> void out(const T&... a) { (std::cout << ... << a); }
void print() {
out('\n');
// std::cout.flush();
}
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {
out(head);
if (sizeof...(Tail)) out(' ');
print(tail...);
}
// for interactive problems
void printflush() {
out('\n');
std::cout.flush();
}
template <class Head, class... Tail> void printflush(Head&& head, Tail&&... tail) {
out(head);
if (sizeof...(Tail)) out(' ');
printflush(tail...);
}
// bool output
void YES(bool t = 1) { print(t ? "YES" : "NO"); }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { print(t ? "Yes" : "No"); }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { print(t ? "yes" : "no"); }
void no(bool t = 1) { yes(!t); }
void POSSIBLE(bool t = 1) { return print(t ? "POSSIBLE" : "IMPOSSIBLE"); }
void Possible(bool t = 1) { return print(t ? "Possible" : "Impossible"); }
void possible(bool t = 1) { return print(t ? "possible" : "impossible"); }
// I/O speed up
struct SetUpIO {
SetUpIO() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout << std::fixed << std::setprecision(15);
}
} set_up_io;
struct Modint261 {
static constexpr unsigned long long m = (1ULL << 61) - 1;
using mint = Modint261;
unsigned long long _v;
static constexpr long long mod() { return m; }
static constexpr unsigned long long umod() { return m; }
Modint261() : _v(0ULL) {}
template <class T> Modint261(T v) {
long long x = (long long)(v % (long long)(umod()));
if (x < 0) x += umod();
_v = (unsigned long long)(x);
}
unsigned long long val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v -= rhs._v;
if (_v >= umod()) _v += umod();
return *this;
}
mint& operator*=(const mint& rhs) {
__uint128_t z = _v;
z *= rhs._v;
z = (z >> 61) + (z & umod());
if (z >= umod()) z -= umod();
_v = (unsigned long long)z;
return *this;
}
mint& operator/=(const mint& rhs) { return (*this *= rhs.inv()); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(n >= 0);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const { return pow(umod() - 2); }
friend mint operator+(const mint& lhs, const mint& rhs) { return mint(lhs) += rhs; }
friend mint operator-(const mint& lhs, const mint& rhs) { return mint(lhs) -= rhs; }
friend mint operator*(const mint& lhs, const mint& rhs) { return mint(lhs) *= rhs; }
friend mint operator/(const mint& lhs, const mint& rhs) { return mint(lhs) /= rhs; }
friend bool operator==(const mint& lhs, const mint& rhs) { return lhs._v == rhs._v; }
friend bool operator!=(const mint& lhs, const mint& rhs) { return lhs._v != rhs._v; }
friend std::ostream& operator<<(std::ostream& os, const mint& v) { return os << v.val(); }
};
using mint261 = Modint261;
template <class Mint> struct RollingHash {
std::vector<Mint> pwr;
const Mint base;
static inline Mint generate_base() {
std::mt19937_64 mt(std::chrono::steady_clock::now().time_since_epoch().count());
std::uniform_int_distribution<uint64_t> rand(1, Mint::mod() - 1);
return Mint(rand(mt));
}
void extend() {
int n = pwr.size();
int m = n * 2;
pwr.resize(m);
for (int i = n; i < m; i++) pwr[i] = pwr[i - 1] * base;
}
RollingHash(int N = 0, Mint base = generate_base()) : base(base) {
pwr.resize(1, Mint(1));
while (N >= (int)pwr.size()) extend();
}
Mint power(int i) { // return base ^ i
assert(i >= 0);
while (i >= (int)pwr.size()) extend();
return pwr[i];
}
std::vector<Mint> build(const std::string& s) const {
int N = (int)s.size();
std::vector<Mint> res(N + 1);
for (int i = 0; i < N; i++) {
res[i + 1] = res[i] * base + s[i];
}
return res;
}
template <class T> std::vector<Mint> build(const std::vector<T>& s) const {
int N = (int)s.size();
std::vector<Mint> res(N + 1);
for (int i = 0; i < N; i++) {
res[i + 1] = res[i] * base + s[i];
}
return res;
}
Mint prod(const std::vector<Mint>& hs, int l, int r) {
assert(0 <= l and l <= r and r < hs.size());
return hs[r] - hs[l] * power(r - l);
}
Mint combine(Mint h1, Mint h2, int h2len) { return h1 * power(h2len) + h2; }
};
#include <atcoder/convolution>
using namespace std;
int main() {
INT(N, M, K);
STR(S, T);
vector<i64> sl(N), tl(M), sa(N), ta(M);
REP(i, N) {
if ('A' <= S[i] and S[i] <= 'Z') {
sa[i] = S[i] - 'A';
sl[i] = 0;
} else {
sa[i] = S[i] - 'a';
sl[i] = 1;
}
}
REP(i, M) {
if ('A' <= T[i] and T[i] <= 'Z') {
ta[i] = T[i] - 'A';
tl[i] = 0;
} else {
ta[i] = T[i] - 'a';
tl[i] = 1;
}
}
auto conv = [](vector<i64> s, vector<i64> t) -> vector<i64> {
auto c = atcoder::convolution_ll(s, t);
int n = LEN(s), m = LEN(t);
i64 tsum = 0;
REP(i, m) tsum += t[i] * t[i];
i64 ssum = 0;
REP(i, m) ssum += s[i] * s[i];
REP(i, n - m + 1) {
c[i + m - 1] = ssum - 2 * c[i + m - 1] + tsum;
ssum -= s[i] * s[i];
if (i + m < n) ssum += s[i + m] * s[i + m];
}
return c;
};
REV(tl);
auto cl = conv(sl, tl);
RollingHash<mint261> rh;
auto rhs = rh.build(sa);
auto rht = rh.build(ta);
int ans = 0;
REP(i, N - M + 1) {
if (rh.prod(rhs, i, i + M) == rh.prod(rht, 0, M) and cl[i + M - 1] > 0 and cl[i + M - 1] <= K) {
ans++;
}
}
print(ans);
return 0;
}