AtCoder Regular Contest 024 C - だれじゃ
解法
アナグラムダジャレであるということは、2つの文字列に同じ文字が同じだけ含まれているということなので、各アルファベットが何個含まれているかを累積和的に更新しながら探す感じでやる。
なぜか一致判定にローリングハッシュを使ってしまったけど、vectorをsetに突っ込んでも間に合うっぽい。
実装
// C #ifndef _GLIBCXX_NO_ASSERT #include <bits/stdc++.h> using namespace std; #define int long long typedef unsigned long long ull; const ull B = 11451418931919; const int MAX_N = 100000; int N, K; string S; set<ull> hashSet; ull ToHash(int cnt[26]) { ull w = 1, res = 0; for (int i = 0; i < 26; i++) { res += cnt[i] * w; w *= B; } return res; } bool Solve() { int cnt[26] = {}; ull add[MAX_N] = {}; for (int i = 0; i < K; i++) cnt[S[i] - 'a']++; for (int i = 0; i + K - 1 < N; i++) { if (i >= K) hashSet.insert(add[i]); add[i + K] = ToHash(cnt); if (hashSet.find(add[i + K]) != hashSet.end()) return true; cnt[S[i] - 'a']--; if (i + K < N) cnt[S[i + K] - 'a']++; } return false; } signed main() { cin >> N >> K >> S; puts(Solve() ? "YES" : "NO"); return 0; }