Cod sursa(job #2841122)

Utilizator Theo14Ancuta Theodor Theo14 Data 29 ianuarie 2022 12:22:15
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include<bits/stdc++.h>
#define base 75
#define hash1 666013
using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

char a[2000002],b[2000002];
vector<int>v;

int main()
{
    f>>a>>b;
    int n=strlen(a),val=0,m=strlen(b),nou=0,k=0,basel=1,i;
    for(i=0;i<n;i++)
    {
        val=(val*base+(a[i]-'0'))%hash1;
    }
    for(i=0;i<n;i++)
    {
        nou=(nou*base+(b[i]-'0'))%hash1;
    }
    for(i=0;i<n-1;i++)
    {
        basel=(basel*base)%hash1;
    }
    if(nou==val)
    {
        k++;
        v.push_back(0);
    }
    for(i=n;i<m;i++)
    {
        nou=(nou-(b[i-n]-'0')*basel)%hash1;
        if(nou<0)
            nou+=hash1;
        nou*=base;
        nou=nou+b[i]-'0';
        nou%=hash1;
        if(nou==val)
        {
            k++;
            if(k<1000)
                v.push_back(i-n+1);
        }
    }
    g<<k<<'\n';
    for(auto it:v)
        g<<it<<" ";
    return 0;
}