[해싱] 백준 10840번 구간 성분

문제

매 초마다 신호를 발생시키는 두 장치 A, B가 있다. 이 신호는 알파벳 소문자의 서열로 표현된다. A, B로부터 발생한 신호를 서열로 표시한 SA, SB의 예는 다음과 같다.

• SA = [a, f, c, d, r, d, e, s, d, c, f, w, s, z, r]
• SB = [g, e, d, s, r, d, d, e, m, z, r]

신호 서열의 어떤 구간에 포함된 문자의 종류와 개수가 순서에 상관없이 동일하면 이 두 ‘구간의 성분’은 같다고 한다. 아래에서 박스로 표시된 부분은 두 신호 SA, SB에서 성분이 같은 구간을 나타내고 있다.

즉 위의 예와 같이 성분이 같은 구간의 길이는 두 서열에서 반드시 같아야 한다. 그리고 같은 성분 의 구간은 하나 이상 존재할 수 있다. 우리는 두 신호 서열에 각각 존재하는 같은 성분 구간 중에 서 가장 긴 것을 찾으려고 한다.

입력

첫 두 줄에 신호 서열이 공백 없는 하나의 문자열로 각각 주어진다. 이 문자열은 영문 소문자로만 구성되어 있다. 두 입력 문자열의 크기 N, M의 범위는 1 ≤ N, M ≤ 1,500 이다.

출력

두 서열에서 같은 성분을 가진 구간 중에서 가장 긴 구간을 찾아, 그 구간의 길이를 출력해야 한다. 

 

 

1. 브루트포스 => 시간초과  4중 포문 ( substr 후 sort )

2. map => 메모리 초과

3. set => 아슬아슬 통과

 

아이디어는 길이 1부터 str.size()까지 끊어가면서 알파벳 빈도 체크.

그리고 set에 저장한 후에 똑같이 다음 스트링에서 반복하면서 해당 빈도가 set에 저장되 있는지 확인하고

있다면 길이 갱신.

 

#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<stack>
#include<set>
#include<map>
using namespace std;

set<vector<int> > m;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	string str1;
	string str2;
	cin >> str1 >> str2;
	int ans = 0;
	int len1 = str1.length();
	int len2 = str2.length();

	for (int len = 1; len <= len1; len++)
	{
		int s = 0; 
		int e = len - 1;
		vector<int> vec(26);
		for (int i = s; i <= e; i++)
			vec[str1[i] - 'a']++;

		while (e < len1)
		{
			m.insert(vec);
			if (++e < len1)
			{
				vec[str1[e] - 'a']++;
				vec[str1[s++] - 'a']--;
			}
		}
	}

	for (int len = 1; len <= len2; len++)
	{
		int s = 0;
		int e = len - 1;
		vector<int> vec(26);
		for (int i = s; i <= e; i++)
			vec[str2[i] - 'a']++;

		while (e < len2)
		{
			if (m.count(vec))
				ans = max(ans, len);
				
				
			if (++e < len2)
			{
				vec[str2[e] - 'a']++;
				vec[str2[s++] - 'a']--;
			}
		}
	}

	cout << ans << endl;
}