맵(map || unordered_map) 자료구조를 활용한 해쉬 슬라이딩, 아나그램 찾기 문제 in C++
7906 단어 hash slidingMapMap
두개의 문자열이 주어질때, 첫 번째 문자열에서 두 번째 문자열에 해당하는 아나그램의 총 개수를 출력하는 코드
#include <bits/stdc++.h>
using namespace std;
int cnt = 0;
string s, t;
unordered_map<char, int> s_map, t_map;
int main() {
ios_base::sync_with_stdio(false);
freopen("input.txt", "rt", stdin);
cin >> s >> t;
for(int i=0; i<t.size(); i++) {
t_map[t[i]]++;
}
for(int i=0; i<t.size()-1; i++) {
s_map[s[i]]++;
}
int lt = 0;
for(int rt=t.size()-1; rt<s.size(); rt++) {
s_map[s[rt]]++;
if(t_map == s_map) cnt++;
for(auto it : s_map) {
cout << it.first << ":"<< it.second << " ";
}
cout << '\n';
s_map[s[lt]]--;
if(s_map[s[lt]] == 0) s_map.erase(s[lt]);
lt++;
}
cout << cnt;
return 0;
}
- unordered_map : 충분히 큰 사이즈에서는 map 자료구조가 더빠르지만, 알고리즘을 공부하는 간단한 수준에서는 unodered_map의 속도가 더욱 빠르다.
- s_map[s[rt]]++ , s_map[s[lt]]-- : 해쉬 슬라이딩
- if(s_map[s[lt]]) == 0) s_map.erase(s[lt]) : lt에 해당하는 부분을 감소시켰을때, 0이라면 s_map에서 데이터 값 s[lt]에 해당하는 부분을 삭제한다.
ex)
eabcbacade
abc
Author And Source
이 문제에 관하여(맵(map || unordered_map) 자료구조를 활용한 해쉬 슬라이딩, 아나그램 찾기 문제 in C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@juwon9733/맵map-unorderedmap-자료구조를-활용한-해쉬-슬라이딩-아나그램-찾기-문제-in-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)