Submission #134258

#	Time	Username	Problem	Language	Result	Execution time	Memory
134258		ansol4328	구간 성분 (KOI15_interval)	C++11	100 / 100	267 ms	632 KiB

interval

#include<stdio.h>
#include<string.h>
#include<vector>
#include<utility>
#include<algorithm>

using namespace std;
typedef long long ll;
typedef pair<ll,int> P;

int n, m;
char s1[1505], s2[1505];
ll eval[30];
const ll MOD=1e9+7, e=1501;

void Hashing(int len, vector<P> &lst)
{
    ll val=0;
    for(int i=1 ; i<=len ; i++) (val+=eval[s1[i]-'a'])%=MOD;
    lst.push_back(P(val,1));
    for(int i=len+1 ; i<=n ; i++)
    {
        val=(val-eval[s1[i-len]-'a']+MOD)%MOD;
        (val+=eval[s1[i]-'a'])%=MOD;
        lst.push_back(P(val,i-len+1));
    }
    sort(lst.begin(),lst.end());
}

int get_st(ll val, vector<P> &lst)
{
    int st=0, fn=lst.size()-1, mid, idx=-1;
    while(st<=fn)
    {
        mid=(st+fn)>>1;
        if(lst[mid].first<val) st=mid+1;
        else fn=mid-1, idx=mid;
    }
    if(idx==-1 || lst[idx].first!=val) return -1;
    return idx;
}

int get_fn(ll val, vector<P> &lst)
{
    int st=0, fn=lst.size()-1, mid, idx=-1;
    while(st<=fn)
    {
        mid=(st+fn)>>1;
        if(lst[mid].first>val) fn=mid-1;
        else st=mid+1, idx=mid;
    }
    if(idx==-1 || lst[idx].first!=val) return -1;
    return idx;
}

bool correct(int st1, int st2, int len)
{
    int cnt1[30]={0,};
    int cnt2[30]={0,};
    for(int i=st1 ; i<st1+len ; i++) cnt1[s1[i]-'a']++;
    for(int i=st2 ; i<st2+len ; i++) cnt2[s2[i]-'a']++;
    for(int i=0 ; i<26 ; i++) if(cnt1[i]!=cnt2[i]) return false;
    return true;
}

bool Matching(int len, vector<P> &lst)
{
    ll val=0;
    for(int i=1 ; i<=len ; i++) (val+=eval[s2[i]-'a'])%=MOD;
    int s=get_st(val,lst);
    int f=get_fn(val,lst);
    if(s!=-1 && f!=-1)
    {
        for(int i=s ; i<=f ; i++)
        {
            if(correct(lst[i].second,1,len)) return true;
        }
    }
    for(int i=len+1 ; i<=m ; i++)
    {
        val=(val-eval[s2[i-len]-'a']+MOD)%MOD;
        (val+=eval[s2[i]-'a'])%=MOD;
        s=get_st(val,lst);
        f=get_fn(val,lst);
        if(s!=-1 && f!=-1)
        {
            for(int j=s ; j<=f ; j++)
            {
                if(correct(lst[j].second,i-len+1,len)) return true;
            }
        }
    }
    return false;
}

int main()
{
    scanf("%s",&s1[1]);
    scanf("%s",&s2[1]);
    n=strlen(&s1[1]), m=strlen(&s2[1]);
    eval[0]=1;
    for(int i=1 ; i<26 ; i++) eval[i]=(eval[i-1]*e)%MOD;
    for(int i=min(n,m) ; i>0 ; i--)
    {
        vector<P> lst;
        Hashing(i,lst);
        if(Matching(i,lst))
        {
            printf("%d",i);
            return 0;
        }
    }
    printf("0");
    return 0;
}

Compilation message (stderr)

interval.cpp: In function 'int main()':
interval.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",&s1[1]);
     ~~~~~^~~~~~~~~~~~~
interval.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",&s2[1]);
     ~~~~~^~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 31 / 31
• Subtask 4: 39 / 39