Cod sursa(job #2694781)

Utilizator sims_glAlexandru Simion sims_gl Data 10 ianuarie 2021 18:44:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include<fstream>
#include<cstring>
#include<iostream>
#define P 73
#define MOD1 100007
#define MOD2 100021
using namespace std;

int i, nr=0, H, H2, has, has2, v[1005];
char m[2000003], n[2000004];
int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    cin>>m>>n;
    int l1= strlen(m);
    int l2= strlen(n);
    for(int i=0; i<l1; i++)
    {
        int x= m[i];
        H = (H*P + x)%MOD1;
        H2= (H2*P + x)%MOD2;
    }

    for(int i= 0; i<l1;i++)
    {
        int y= n[i];
        has = (has*P + y)%MOD1;
        has2 = (has2 *P+ y)%MOD2;
    }
    int pow1=1, pow2=1;
    for(int i=1; i<l1;i++)
    {
        pow1=(pow1* P)%MOD1;
        pow2= (pow2 * P)%MOD2;
    }
    if(has== H && has2== H2)
    {
        nr++;
    }
    for(int i= l1; i<l2;i++)
    {
        has = (has-pow1*(n[i-l1]))%MOD1+ MOD1;
        has= (has*P +(n[i]))%MOD1;

        has2 = (has2-pow2*(n[i-l1]))%MOD2+MOD2;
        has2= (has2*P +(n[i]))%MOD2;
        if(has==H && has2== H2)
        {
            nr++;
            if(nr<=1000)
            v[nr]=i-l1+1;
        }
    }
    cout << nr<<endl;
    for(int i=1 ;i<=nr && i<=1000;i++)
        cout<<v[i]<<" ";
}