Cod sursa(job #3337712)

Utilizator jarnea_justinjarnea justin ioan jarnea_justin Data 29 ianuarie 2026 16:23:07
Problema Potrivirea sirurilor Scor 86
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const unsigned long long M=1e9+13;
unsigned long long h1[2000005],h,p1=37,p[2000005],n,m,sol[1005],i,q,j,k;
string s1,s2;
int main()
{
    f>>s1>>s2;
    n=s1.size();
    m=s2.size();
    h=0;
    h1[0]=0;
    p[0]=1;
    for(i=1;i<=n;i++)
        h=(h*p1+(int)s1[i-1]);

    for(i=1;i<=m;i++)
    {
        h1[i]=(h1[i-1]*p1+(int)s2[i-1]);
        p[i]=p[i-1]*p1;
    }
    for(i=0;i<m-n+1;i++)
    {
        j=i+n-1;
        k=h1[j+1]-h1[i]*p[j-i+1];
        if(k==h)
            sol[++q]=i;
    }
    g<<q<<'\n';
    if(q>1000)
        q=1000;
    for(i=1;i<=q;i++)
        g<<sol[i]<<" ";
    return 0;
}