Cod sursa(job #2763712)

Utilizator DavidAA007Apostol David DavidAA007 Data 16 iulie 2021 12:03:45
Problema Potrivirea sirurilor Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include<iostream>
#include<fstream>
#include<string.h>
#define mod 100007
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char sir1[2000005],sir2[2000005];
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]-'A'+1;
        nr1=(nr1*27+nr)%mod;
    }
    putere=1;
    for(i=0;i<n;i++)
    {
        if(i>0)
            putere=(putere*27)%mod;
        nr=sir2[i]-'A'+1;
        nr2=(nr2*27+nr)%mod;
    }
    if(nr2==nr1)
        c++;
    ultima=nr;
    for(i=n;i<m;i++)
    {
        nr=sir2[i]-'A'+1;
        prima=sir2[i-n]-'A'+1;
        nr2=(nr2-prima*putere)%mod;
        nr2=(nr2+mod)%mod;
        nr2=(nr2*27+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*27)%mod;
        nr=sir2[i]-'A'+1;
        nr2=(nr2*27+nr)%mod;
    }
    if(nr2==nr1)
        c++;
    ultima=nr;
    for(i=n;i<m;i++)
    {
        nr=sir2[i]-'A'+1;
        prima=sir2[i-n]-'A'+1;
        nr2=(nr2-prima*putere)%mod;
        nr2=(nr2+mod)%mod;
        nr2=(nr2*27+nr)%mod;
        //cout<<nr2<<" "<<nr1<<"\n";
        if(nr2==nr1)
        {
            fout<<i-n+1<<" ";
            c++;
        }
    }
    fin.close();
    fout.close();
    return 0;
}