[10840번] 구간 성분

문제 출처 :

https://www.acmicpc.net/problem/10840

알고리즘 분석 :

문제 해결에 필요한 사항

1. set STL

각각의 첫번째 스트링과 두번째 스트링의 1~len1 과 1~len2에 대한 모든 구간에 대한 알파벳 수를 set에 담아주고 비교를 해주면 문제를 해결 할 수 있다.

이렇게 문제를 해결하면 대략 900ms가 나오는데 set을 set<vector<int> > se[1501]으로 잡고 각 길이에 맞게 set에 집어넣어 준 후

se[1500]부터 se[1]까지 역으로 봐준다면 아래 코드 se에 모든 것을 다 집어넣는 것이 아니니 

트리의 크기도 줄 수 있고, cutting효과도 낼 수 있다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
set<vector<int>> se;
 
int main()
{
    char str1[1502];
    char str2[1502];
    int ans = 0;
 
    scanf("%s %s", str1, str2);
 
    int len1 = strlen(str1);
    int len2 = strlen(str2);
 
    for (int len = 1; len <= len1; len++)
    {
        int s = 0, e = len - 1;
        vector<int> vc(26);
 
        for (int i = s; i <= e; i++)
            vc[str1[i] - 'a']++;
 
        while (e < len1)
        {
            se.insert(vc);
 
            if (++e < len1)
            {
                vc[str1[e] - 'a']++;
                vc[str1[s++] - 'a']--;
            }
        }
    }
 
    for (int len = 1; len <= len2; len++)
    {
        int s = 0, e = len - 1;
        vector<int> vc(26);
        for (int i = s; i <= e; i++)
            vc[str2[i] - 'a']++;
 
        while (e < len2)
        {
            if (se.count(vc))
                ans = max(ans, len);
 
            if (++e < len2)
            {
                vc[str2[e] - 'a']++;
                vc[str2[s++] - 'a']--;
            }
        }
    }
 
    cout << ans;
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>