[BOJ] 10840 구간 성분

진짜 어이없게 풀었다. 처음에는 해싱인지 모르고 $O(n^3)$에 최적화 생각했는데

롤링 해시 구현하기 귀찮아서 그냥 알파벳에 숫자 하나씩 할당해 놓고 다 더한다음에 일치하면 okay라고 판별했다.

int 범위 내에서 하니까 충돌나길래 long long 범위까지 늘렸더니 어셉됐다 ㅋㅋㅋㅋㅋㅋ

결과적으로는 $O(n^2 lg n) 풀이임.

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cassert>
 
using namespace std;
 
typedef long long ll;
 
ll prime[]={1553543355441,6835413543356,341238467843,5846878493734,255654493854,4385646055553,29333247254,56842665466513,6562454444132,33264680204,97185465094454,8937264644356,85143166465423,78565446465415,98746146556215,8547654654856,841537879874131,7293864657254,9814378779242,74464658844594,24495564314761,186549524066569,39665654465873,481654731322,41565458484,13646542908};
 
int ctoi(char x)
{
    return x-'a';
}
 
int main()
{
    char a[1505],b[1505];
    scanf("%s %s",a,b);
    int alen=strlen(a);
    int blen=strlen(b);
 
    /*for(int i=0;i<26;i++)
        assert(isPrime(prime[i]));*/
 
    ll asum[1505]={},bsum[1505]={};
    for(int i=1;i<=alen;i++)
        asum[i]=asum[i-1]+prime[ctoi(a[i-1])];
    for(int i=1;i<=blen;i++)
        bsum[i]=bsum[i-1]+prime[ctoi(b[i-1])];
    vector<ll> V;
    for(int i=1;i<=alen;i++)
        for(int j=i;j<=alen;j++)
            V.push_back(asum[j]-asum[i-1]);
    sort(V.begin(),V.end());
    for(int i=blen;i>=1;i--)
    {
        for(int j=0;j<=blen-i;j++)
        {
            if(binary_search(V.begin(),V.end(),bsum[i+j]-bsum[j]))
            {
                printf("%d",i);
                return 0;
            }
        }
    }
    printf("0");
    return 0;
}