Cod sursa(job #3232184)

Utilizator mihneatoadergabrielToader Mihnea mihneatoadergabriel Data 29 mai 2024 10:46:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.05 kb
/*#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");

long long v1,v2,na,nb,h1,h2,p1,p2,m1,m2,i,sol[10005],nr,k;
char a[2000050],b[2000050];
int main()
{
    in.getline(a,2000050);
    in.getline(b,2000050);

    na=strlen(a),nb=strlen(b);
    p1=p2=1;
    v1=v2=0;
    h1=h2=0;
    m1=666013;
    m2=10003;
    for(i=0;i<na;i++)
    {
        h1=(h1*127+a[i])%m1;
        h2=(h2*127+a[i])%m2;
        if(i!=0)  p1=(p1*127)%m1,
                  p2=(p2*127)%m2;
        v1=(v1*127+b[i])%m1;
        v2=(v2*127+b[i])%m2;
    }
    for(i=na;i<nb;++i){
        v1=((v1-(b[i-na]*p1)%m1+m1)*127+b[i])%m1;
        v2=((v2-(b[i-na]*p2)%m2+m2)*127+b[i])%m2;
        if(v1==h1 && v2==h2) {nr++; if(k<=999)sol[++k]=i-na+1;}
    }
    out<<nr<<endl;
    for(i=1;i<=k;i++)
    {
        out<<sol[i]<<' ';
    }
    return 0;
}*/
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

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

const int mod1 = 666013;
const int mod2 = 10005;
const int nmaxx = 2000005;

long long n, m, sumok1, sumok2, sumi1, sumi2, p1 = 1, p2 = 1;
char a[nmaxx], b[nmaxx];
vector<int> v;

int main()
{
    f >> a >> b;
    n = strlen(a);
    m = strlen(b);

    for(int i = 0; i < n; i ++)
    {
        sumok1 = (sumok1 * 127 + a[i]) % mod1;
        sumok2 = (sumok2 * 127 + a[i]) % mod2;

        if(i != 0)
        {
            p1 = (p1 * 127) % mod1;
            p2 = (p2 * 127) % mod2;
        }

        sumi1 = (sumi1 * 127 + b[i]) % mod1;
        sumi2 = (sumi2 * 127 + b[i]) % mod2;
    }

    if(sumi1 == sumok1 && sumi2 == sumok2)
        v.push_back(0);

    for(int i = n; i < m; i ++)
    {
        sumi1 = ((sumi1 - (b[i - n] * p1) % mod1 + mod1) * 127 + b[i]) % mod1;

        sumi2 = ((sumi2 - (b[i - n] * p2) % mod2 + mod2) * 127 + b[i]) % mod2;

        if(sumi1 == sumok1 && sumi2 == sumok2)
            v.push_back(i - n + 1);
    }

    int nr = v.size();

    g << nr << '\n';
    for(int i = 0; i < min(nr, 1000); i ++)
        g << v[i] << " ";
    return 0;
}