Cod sursa(job #3231672)

Utilizator brianabucur11Briana Bucur brianabucur11 Data 27 mai 2024 15:51:40
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>

using namespace std;

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

const int p=27;
const int MOD1=666013;
const int MOD2=10003;

int k, sol[2000005];
map <int,bool> mp;
string a, b;

int main()
{
    fin >> a >> b;
    int n=a.size();
    int m=b.size();
    int p1=0, p2=0;
    int h1=0, h2=0;
    for (int i=0; i<n; i++)
    {
        h1=(h1*p+a[i])%MOD1;
        h2=(h2*p+a[i])%MOD2;
        if (i!=0){
        p1=(p1*p)%MOD1;
        p2=(p2*p)%MOD2;}
    }
    int v1=0, v2=0;
    for (int i=0; i<n; i++)
    {
        v1=(v1*p+b[i])%MOD1;
        v2=(v2*p+b[i])%MOD2;
    }
    if (v1==h1 && v2==h2)
        sol[++k]=0;
    for (int i=n; i<m; i++)
    {
        v1=((v1-(b[i-n]*p1)%MOD1+MOD1)*p+b[i])%MOD1;
        v2=((v2-(b[i-n]*p2)%MOD2+MOD2)*p+b[i])%MOD2;
        if (v1==h1 && v2==h2)
            sol[++k]=i-n+1;
    }
    fout << k << '\n';
    k=min(k,1000);
    sort(sol+1,sol+k+1);
    for (int i=1; i<=k; i++)
    {
        if (!mp[sol[i]])
            fout << sol[i] << " ";
        mp[sol[i]]=1;
    }
    return 0;
}