Cod sursa(job #2974189)

Utilizator ana_valeriaAna Valeria Duguleanu ana_valeria Data 3 februarie 2023 15:26:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.05 kb
#include <fstream>
#include <cstring>
#define MOD1 1000000007
#define MOD2 1000000009
#define b 62
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
char s1[2000010],s2[2000010];
int v[1010];
int transforma(char ch)
{
    int val;
    if ('a'<=ch && ch<='z')
        val=ch-'a';
    if ('A'<=ch && ch<='Z')
        val=ch-'A'+26;
    if ('0'<=ch && ch<='9')
        val=ch-'0'+52;
    return val;
}
int main()
{
    long long n1,n2,nr1_mod1,nr1_mod2,nr2_mod1,nr2_mod2,b_putere_mod1,b_putere_mod2,i,ct=0,inc,sf;
    cin>>s1>>s2;
    n1=strlen(s1);
    n2=strlen(s2);
    b_putere_mod1=1;
    b_putere_mod2=1;
    nr1_mod1=transforma(s1[n1-1]);
    nr1_mod2=transforma(s1[n1-1]);
    nr2_mod1=transforma(s2[n1-1]);
    nr2_mod2=transforma(s2[n1-1]);
    for (i=n1-2; i>=0; i--)
    {
        b_putere_mod1=(b_putere_mod1*b)%MOD1;
        b_putere_mod2=(b_putere_mod2*b)%MOD2;
        nr1_mod1=(nr1_mod1+b_putere_mod1*transforma(s1[i])%MOD1)%MOD1;
        nr1_mod2=(nr1_mod2+b_putere_mod2*transforma(s1[i])%MOD2)%MOD2;
        nr2_mod1=(nr2_mod1+b_putere_mod1*transforma(s2[i])%MOD1)%MOD1;
        nr2_mod2=(nr2_mod2+b_putere_mod2*transforma(s2[i])%MOD2)%MOD2;
    }
    if (nr1_mod1==nr2_mod1 && nr1_mod2==nr2_mod2)
    {
        ct++;
        v[ct]=0;
    }
    for (i=n1; i<=n2-1; i++)
    {
        inc=i-n1+1;
        sf=i;
        nr2_mod1=(nr2_mod1-b_putere_mod1*transforma(s2[inc-1])%MOD1+MOD1)%MOD1;
        nr2_mod1=nr2_mod1*b%MOD1;
        nr2_mod1=(nr2_mod1+transforma(s2[sf]))%MOD1;
        nr2_mod2=(nr2_mod2-b_putere_mod2*transforma(s2[inc-1])%MOD2+MOD2)%MOD2;
        nr2_mod2=nr2_mod2*b%MOD2;
        nr2_mod2=(nr2_mod2+transforma(s2[sf]))%MOD2;
        if (nr1_mod1==nr2_mod1 && nr1_mod2==nr2_mod2)
        {
            ct++;
            if (ct<=1000)
                v[ct]=inc;
        }
    }
    cout<<ct<<"\n";
    if (ct<=1000)
        for (i=1; i<=ct; i++)
            cout<<v[i]<<" ";
    else
        for (i=1; i<=1000; i++)
            cout<<v[i]<<" ";
    return 0;
}