Cod sursa(job #3208831)

Utilizator Ruxxi7Ruxandra Gheorghe Ruxxi7 Data 1 martie 2024 10:26:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <bits/stdc++.h>
#define mod1 666013
#define mod2 1000003
using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");

int rptl(int b,int e,int mod){
    int rez=1;
    while(e!=0){
        if(e%2==0){
            b=(1LL*b*b)%mod;
            e/=2;
        }
        else
        {
            rez=(1LL*rez*b)%mod;
            --e;
        }
    }
    return rez;
}
int v[1001];
char s1[2000001],s2[2000001];
int main()
{
    int i,l1,l2;
    int val1_1,val1_2,val2_1,val2_2;
    val1_1=val1_2=val2_1=val2_2=0;

    in>>s1;
    in>>s2;
    l1=strlen(s1);
    l2=strlen(s2);
    int putere1=rptl(67,l1-1,mod1);
    int putere2=rptl(67,l1-1,mod2);
    if(l2<l1)
        out<<0;
    else{
        long long cnt=0;
        for(i=0;i<l1;++i){
            val1_1=(1LL*val1_1*67+s1[i])%mod1;
            val1_2=(1LL*val1_2*67+s1[i])%mod2;
        }
        for(i=0;i<l1;++i){
            val2_1=(1LL*val2_1*67+s2[i])%mod1;
            val2_2=(1LL*val2_2*67+s2[i])%mod2;
        }
        if(val1_1==val2_1&&val1_2==val2_2){
            ++cnt;
            v[cnt]=0;
        }
        for(i=l1;i<l2;++i){
            val2_1=((val2_1-1LL*s2[i-l1]*putere1%mod1+mod1)*67+s2[i])%mod1;
            val2_2=((val2_2-1LL*s2[i-l1]*putere2%mod2+mod2)*67+s2[i])%mod2;
            if(val1_1==val2_1&&val1_2==val2_2){
                ++cnt;
            if(cnt<=1000)
                v[cnt]=i-l1+1;
            }

        }
        out<<cnt<<'\n';
        for(i=1;i<=cnt&&i<=1000;++i)
            out<<v[i]<<" ";
    }
    return 0;
}