Cod sursa(job #3200988)

Utilizator luca.pislaruDocOck luca.pislaru Data 6 februarie 2024 13:44:09
Problema Potrivirea sirurilor Scor 28
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include<fstream>
#include<cstring>
#define MOD1 100007
#define MOD2 100021
using namespace std;
char s1[2000002], s2[2000002];
bool v[2000002];
int main()
{
    ifstream cin ("strmatch.in");
    ofstream cout("strmatch.out");
    int l1, l2, nr1=0, nr2=0, nrs1=0, nrs2=0, p1=1, p2=1, i, cnt=0;
    cin.getline(s1, 2000002);
    cin.getline(s2, 2000002);
    l1=strlen(s1);
    l2=strlen(s2);
    if (l1>l2)
    {
        cout<<'0';
    }
    else
    {
        for (i=0;i<l1;i++)
        {
            nr1=(nr1*73+s1[i])%MOD1;
            nr2=(nr2*73+s1[i])%MOD2;
            if (i>=1)
            {
                p1=(p1*73)%MOD1;
                p2=(p2*73)%MOD2;
            }
        }
        for (i=0;i<l1;i++)
        {
            nrs1=(nrs1*73+s2[i])%MOD1;
            nrs2=(nrs2*73+s2[i])%MOD2;
        }
        if (nrs1==nr1 && nrs2==nr2)
        {
            v[0]=1;
            cnt++;
        }
         for (i=l1;i<l2;i++)
         {
             nrs1=((nrs1-(s2[i-l1]*p1)%MOD1+MOD1)*73+s2[i])%MOD1;
             nrs2=((nrs2-(s2[i-l1]*p2)%MOD2+MOD2)*73+s2[i])%MOD2;
             if (nrs1==nr1 && nrs2==nr2)
             {
                 v[i-l1+1]=1;
                 cnt++;
             }
         }
         cout<<cnt<<'\n';
         for (i=0;i<=1000;i++)
         {
             if (v[i]==1)
             {
                 cout<<i<<' ';
             }
         }
    }
    return 0;
}