백준 10840 (C++) 구간 성분

최초 업로드: 2025-07-24 21:28:17

최근 수정 시간: 2025-07-24 21:28:17

게시자: rlatjwls3333

카테고리: 백준

# [Gold I] 구간 성분

[문제 링크](https://www.acmicpc.net/problem/10840)

## 문제 설명

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

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

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

## 입력

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

## 출력

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

## 풀이
#### 슬라이딩 윈도우로 개수를 카운팅한 나이브한 벡터를 셋에 넣어 비교했습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string a, b; cin >> a >> b;

for(int len=min(a.length(), b.length());len>0;len--) {
 set<vector<int>> subStrA;

vector<int> cnt(26);
 for(int i=0;i<len;i++) cnt[a[i]-'a']++;
 subStrA.insert(cnt);

int left=0, right=len;
 while(right<a.length()) {
 cnt[a[right++]-'a']++;
 cnt[a[left++]-'a']--;
 subStrA.insert(cnt);
 }

cnt.assign(26, 0);
 for(int i=0;i<len;i++) cnt[b[i]-'a']++;
 if(subStrA.count(cnt)) {
 cout << len;
 return 0;
 }

left=0, right=len;
 while(right<b.length()) {
 cnt[b[right++]-'a']++;
 cnt[b[left++]-'a']--;
 if(subStrA.count(cnt)) {
 cout << len;
 return 0;
 }
 }
 }
 cout << 0;
}
```