Cod sursa(job #2841405)

Utilizator Theo14Ancuta Theodor Theo14 Data 29 ianuarie 2022 17:54:29
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 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()
{
    int i,n,m,base1=1,nr1=0,k=0;
    f>>a>>b;
    n=strlen(a);
    m=strlen(b);
    int nr=0;
    for(i=0;i<n;i++)
    {
        nr=(nr*base+(a[i]-'0'))%hash1;
    }
    for(i=0;i<n-1;i++)
        base1=(base1*base)%hash1;
    for(i=0;i<n;i++)
    {
        nr1=(nr1*base+(b[i]-'0'))%hash1;
    }
    if(nr==nr1)
    {
        k++;
        v.push_back(0);
    }
    for(i=n;i<m;i++)
    {
        nr1=(nr1-(b[i-n]-'0')*base1)%hash1;
        if(nr1<0)
            nr1+=hash1;
        nr1=(nr1*base);
        nr1+=(b[i]-'0');
        nr1%=hash1;
        if(nr1==nr)
        {
            k++;
            if(k<=1000)
                v.push_back(i-n+1);
        }
    }
    g<<k<<'\n';
    for(auto it:v)
        g<<it<<" ";
    return 0;

}