Cod sursa(job #2764334)

Utilizator DavidAA007Apostol David DavidAA007 Data 20 iulie 2021 13:44:23
Problema Potrivirea sirurilor Scor 36
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include<iostream>
#include<fstream>
#include<string.h>
#define mod 100007
#define p 140
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char sir1[2000005],sir2[2000005];
long long int n,m,i,j,c,nr,nr1,nr2,prima,ultima,ind,putere;
int main()
{
    fin.getline(sir1,2000005);
    //cin.get();
    fin.getline(sir2,2000005);
    n=strlen(sir1);
    m=strlen(sir2);
    nr1=0;
    for(i=0;i<n;i++)
    {
        nr=sir1[i];
        nr1=(nr1*p+nr)%mod;
    }
    putere=1;
    for(i=0;i<n;i++)
    {
        if(i>0)
            putere=(putere*p)%mod;
        nr=sir2[i];
        nr2=(nr2*p+nr)%mod;
    }
    if(nr2==nr1)
        c++;
    ultima=nr;
    for(i=n;i<m;i++)
    {
        nr=sir2[i];
        prima=sir2[i-n];
        nr2=(nr2-prima*putere)%mod;
        nr2=(nr2+mod)%mod;
        nr2=(nr2*p+nr)%mod;
        //cout<<nr2<<" "<<nr1<<"\n";
        if(nr2==nr1)
        {
            c++;
        }
    }
    fout<<c<<"\n";
    putere=1;
    nr=0;
    nr2=0;
    for(i=0;i<n;i++)
    {
        if(i>0)
            putere=(putere*p)%mod;
        nr=sir2[i];
        nr2=(nr2*p+nr)%mod;
    }
    if(nr2==nr1)
        c++;
    ultima=nr;
    for(i=n;i<m;i++)
    {
        nr=sir2[i];
        prima=sir2[i-n];
        nr2=(nr2-prima*putere)%mod;
        nr2=(nr2+mod)%mod;
        nr2=(nr2*p+nr)%mod;
        //cout<<nr2<<" "<<nr1<<"\n";
        if(nr2==nr1)
        {
            fout<<i-n+1<<" ";
            c++;
        }
    }
    fin.close();
    fout.close();
    return 0;
}