Cod sursa(job #3206311)

Utilizator BOSSSTEFANPetrescu Ioan Stefan BOSSSTEFAN Data 22 februarie 2024 11:40:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include<fstream>
#include<cstring>
#define MOD1 100007
#define MOD2 100021
using namespace std;
char s1[2000005], s2[2000005];
int rez[1001];
const int b1=127,b2=131;
int main()
{
    ifstream cin ("strmatch.in");
    ofstream cout("strmatch.out");
    long long int l1, l2, nr1=0, nr2=0, nrs1=0, nrs2=0, p1=1, p2=1, i, cnt=0;
    cin>>s1>>s2;
    l1=strlen(s1);
    l2=strlen(s2);
    if (l1>l2)
    {
        cout<<'0';
    }
    else
    {
        for (i=0;i<l1;i++)
        {
            nr1=(nr1*b1+s1[i])%MOD1;
            nr2=(nr2*b2+s1[i])%MOD2;
            if (i>=1)
            {
                p1=(p1*b1)%MOD1;
                p2=(p2*b2)%MOD2;
            }
        }
        for (i=0;i<l1;i++)
        {
            nrs1=(nrs1*b1+s2[i])%MOD1;
            nrs2=(nrs2*b2+s2[i])%MOD2;
        }
        if (nrs1==nr1 && nrs2==nr2)
        {
            rez[++cnt]=0;
        }
         for (i=l1;i<l2;i++)
         {
             nrs1=((nrs1-(p1*s2[i-l1])%MOD1+MOD1)*b1+s2[i])%MOD1;
             nrs2=((nrs2-(p2*s2[i-l1])%MOD2+MOD2)*b2+s2[i])%MOD2;
             if (nrs1==nr1 && nrs2==nr2)
             {
                 cnt++;
                 if(cnt<=1000)
                    rez[cnt]=i-l1+1;
             }
         }
         cout<<cnt<<'\n';
         for (i=1;i<=1000 && i<=cnt;i++)
         {
             cout<<rez[i]<<" ";
         }
    }
    return 0;
}