読者です 読者をやめる 読者になる 読者になる

4bitにっき

ぽよ

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;
}