Cod sursa(job #2841156)

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

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

char a[2000002],b[2000002];
vector<int>v;
int val1=0,val2=0,nou1=0,nou2=0;

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