Cod sursa(job #2967505)

Utilizator Mendea_IanisMendea Ianis Teodor Mendea_Ianis Data 19 ianuarie 2023 18:21:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int mod1 = (1e9)+7,mod2 = (666013);
const int p1 = 61, p2 = 67;

string a,b;

long long h1,h2,z1,z2,plen = 1,p2len = 1;

vector <int> V;

int main()
{
    fin>>a>>b;
    int len = a.size();
    int len2 = b.size();
    for(int i = 1;i<len;i++)
    {
        plen = plen*p1%mod1;
        p2len = p2len*p2%mod2;
    }
    for(int i = 0;i<len;i++)
    {
        h1 = (h1*p1 + a[i])%mod1;
        h2 = (h2*p2 + a[i])%mod2;
    }
    for(int j = 0;j<len;j++)
    {
        z1 = (z1*p1 + b[j])%mod1;
        z2 = (z2*p2 + b[j])%mod2;
    }
    if(h1 == z1 && h2 == z2)
    {
        V.push_back(0);
    }
    for(int i = len;i<len2;i++)
    {
        z1 -= (b[i-len]*plen)%mod1;
        z2 -= (b[i-len]*p2len)%mod2;
        z1 = (z1 + mod1) %mod1;
        z2 = (z2 + mod2) %mod2;
        z1 = (z1*p1 + b[i])%mod1;
        z2 = (z2*p2 + b[i])%mod2;
        if(h1==z1 && h2 == z2)
        {
            V.push_back(i-len+1);
        }
    }
    fout<<V.size()<<'\n';
    for(int i = 0;i<(min((int)V.size(),1000));i++)
    {
        fout<<V[i]<<' ';
    }
}