Cod sursa(job #3210236)

Utilizator MariosulmarioMario Badea Mariosulmario Data 5 martie 2024 16:20:40
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <cstring>
#include <vector>
#define base 54
#define m1 100013
#define m2 100009
using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

vector<int> rasp;
char s1[2000001],s2[2000001];
int nrs1,nrs2,p1,p2;

int main()
{
    cin.get(s1,2000001);
    cin.get();
    cin.get(s2,2000001);
    int ls1=strlen(s1);
    int ls2=strlen(s2);
    nrs1=nrs2=0;
    p1=p2=1;
    for(int i=0;i<ls1;i++){
        nrs1=(nrs1*base+s1[i])%m1;
        nrs2=(nrs2*base+s1[i])%m2;
        if(i>0){
            p1=p1*base%m1;
            p2=p2*base%m2;
        }
    }
    if(ls1>ls2){
        cout<<0;
    }else{
        int nr1=0,nr2=0;
        for(int i=0;i<ls1;i++){
            nr1=(nr1*base+s2[i])%m1;
            nr2=(nr2*base+s2[i])%m2;
        }
        if(nr1==nrs1&&nr2==nrs2){
            rasp.push_back(0);
        }
        for(int i=ls1;i<ls2;i++){
            nr1=((nr1-(s2[i-ls1]*p1)%m1+m1)*base+s2[i])%m1;
            nr2=((nr2-(s2[i-ls1]*p2)%m2+m2)*base+s2[i])%m2;
            if(nr1==nrs1&&nr2==nrs2){
                rasp.push_back(i-ls1+1);
            }
        }
        cout<<rasp.size()<<"\n";
        ls2=rasp.size();
        for(int i=0;i<ls2&&i<1000;i++){
            cout<<rasp[i]<<" ";
        }
    }
}