Submission #20223

#	Time	Username	Problem	Language	Result	Execution time	Memory
20223		ansol4328	구간 성분 (KOI15_interval)	C++98	30 / 100	1078 ms	9 KiB

interval

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

#define Mod1 10007

using namespace std;

struct A
{
    int st, fn;
};

vector<A> hash_table1[Mod1+2];
A in;
char a[1502], b[1502];

bool compair1(int key, int s, int f)
{
    int i, j, len=f-s+1, n=hash_table1[key].size();
    int cnta[30]={0,}, cntb[30]={0,}, ss, ff;
 
    for(i=s ; i<=f ; i++) cntb[b[i]-'a'+1]++;
    for(i=0 ; i<n ; i++)
    {
        ff=hash_table1[key][i].fn, ss=hash_table1[key][i].st;
        if(ff-ss+1==len)
        {
            for(j=ss ; j<=ff ; j++) cnta[a[j]-'a'+1]++;
            for(j=1 ; j<=26 ; j++) if(cnta[j]!=cntb[j]) break;
            if(j>26) break;
        }
        for(j=1 ; j<=26 ; j++) cnta[j]=0;
    }
    if(i<n) return true;
    else return false;
}

int main()
{
    int la, lb, i, j;
    int sum1, out=0;
    bool tf1;

    scanf("%s %s",a,b);
    la=strlen(a), lb=strlen(b);
    for(i=0 ; i<la ; i++)
    {
        sum1=0;
        for(j=i ; j<la ; j++)
        {
            sum1+=(a[j]-'a'+1);
            sum1%=Mod1;
            in.st=i, in.fn=j;
            hash_table1[sum1].push_back(in);
        }
    }
    for(i=0 ; i<lb ; i++)
    {
        sum1=0;
        for(j=i ; j<lb ; j++)
        {
            sum1+=(b[j]-'a'+1);
            sum1%=Mod1;
            tf1=compair1(sum1,i,j);
            if(tf1 && out<j-i+1) out=j-i+1;
        }
    }
    printf("%d",out);
    return 0;
}

Compilation message (stderr)

interval.cpp: In function 'int main()':
interval.cpp:45:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s %s",a,b);
                       ^

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