Idea
S
안에서 단어W
의 순열 중 하나가 부분 문자열로 들어있는 모든 경우의 수를 계산W
의 길이가 g
라고 했을 때, 문자열 S
에서 g
만큼 떼서 보았을 때 그 문자열을 구성하는 각 글자들이 W
를 구성하는 각 글자들과 동일한지 살펴본다S
의 처음부터 g
길이만큼 차례대로 탐색하므로 Sliding Window 기법을 사용 Sliding Window?
Initialise
문자열 W을 저장, 문자열 S에서 문자열 W이 길이만큼의 임시 문자열을 저장할 해쉬 맵을 만들어 준다
문자열 W에서 알파벳 종류의 개수, 임시 문자열에서 알파벳 종류의 개수를 저장해준다
map<char, int> origin;
map<char, int> tmp;
int w_kind = 0; // w문자열의 종류
int s_kind = 0; // s문자열의 종류
for (int i = 0; i < N; i++) {
if (origin.find(W[i]) == origin.end()) {
origin[W[i]] = 1;
w_kind++;
}
else
origin[W[i]]++;
}
// s문자열에서 처음 n개의 문자에 대해 계산
for (int i = 0; i < N; i++) {
if (tmp.find(S[i]) == tmp.end()) {
tmp[S[i]] = 1;
s_kind++;
}
else
tmp[S[i]]++;
}
Sliding Window
W
의 길이 N
만큼 윈도우 크기로 설정int Start = 0;
int End = N - 1;
End
가 문자열 S
의 길이 (M-1)
일때 까지만 반복해서 윈도우를 옮겨준다W
에 있는 알파벳 종류 (w_kind)
와 임시 문자열에 있는 알파벳 종류 (s_kind)
가 같다면 이 두 문자열의 순열이 같은지 계산Source Code
#include <iostream>
#include <map>
using namespace std;
int N, M;
string W, S;
map<char, int> origin;
map<char, int> tmp;
int w_kind = 0; // w문자열의 종류
int s_kind = 0; // s문자열의 종류
int ans = 0;
void sliding_window() {
int Start = 0;
int End = N - 1;
while (1) {
if (s_kind == w_kind) {
bool check = true;
for (int i = Start; i <= End; i++) {
if (tmp[S[i]] != origin[S[i]]) {
check = false;
break;
}
}
if (check) ans++;
}
if (tmp[S[Start]] == 1) {
tmp.erase(S[Start]);
s_kind--;
}
else tmp[S[Start]]--;
Start++; End++;
if (End >= M) break;
if (tmp.find(S[End]) == tmp.end()) {
tmp[S[End]] = 1;
s_kind++;
}
else tmp[S[End]]++;
}
}
void input() {
cin >> N >> M;
cin >> W >> S;
for (int i = 0; i < N; i++) {
if (origin.find(W[i]) == origin.end()) {
origin[W[i]] = 1;
w_kind++;
}
else
origin[W[i]]++;
}
// s문자열에서 처음 n개의 문자에 대해 계산
for (int i = 0; i < N; i++) {
if (tmp.find(S[i]) == tmp.end()) {
tmp[S[i]] = 1;
s_kind++;
}
else
tmp[S[i]]++;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
input();
sliding_window();
cout << ans << endl;
return 0;
}