Cod sursa(job #2763067)

Utilizator KarinAAndrei Karina KarinA Data 11 iulie 2021 14:23:22
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

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

char a[2000005],b[2000005];
const int X=37;
const int MOD=1000007;
vector <int> v;

void citeste()
{
    in>>a;
    in>>b;
}

void solve()
{
    int n=strlen(a),m=strlen(b);
    int hA=0,hB=0,p=1;
    for(int i=0;i<n;i++)
    {
        hA = (hA * X + (a[i] - 'A')) % MOD;
    }

    if(n>m)
    {
        out<<0;
        return;
    }
    for(int i=0;i<n;i++)
    {
        hB = (hB * X + (b[i] - 'A')) % MOD;
    }
    for(int i=1;i<=n-1;i++)
        p*=X;
    if(hB==hA)
    {
        v.push_back(n);
    }
    for(int i=n;i<m;i++)
    {
        hB = ((hB - ((p * (b[i-n] - 'A')) % MOD) + MOD) * X + (b[i] - 'A')) % MOD;
        if(hB==hA)
            v.push_back(i-n+1);
    }
    out<<v.size()<<'\n';
    for(int i=0;i<v.size() && i<1000;i++)
        out<<v[i]<<" ";
}

int main()
{
    citeste();
    solve();
    return 0;
}