Cod sursa(job #3258235)

Utilizator theo_aldescuTheodora Aldescu theo_aldescu Data 21 noiembrie 2024 16:58:31
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.64 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define M 1000000013
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
long long h[2000005],p1,l1,l2,i,x,q,sol[1005],h2,p[2000005],j;
string s1,s2;
int main()
{f>>s1>>s2;
l1=s1.size();
l2=s2.size();
p1=37;
h[0]=0;
p[0]=1;
for(i=1;i<=l1;i++)
    {h2=(h2*p1+(int)s1[i-1])%M;
    }

for(i=1;i<=l2;i++)
    {h[i]=(h[i-1]*p1+(int)s2[i-1])%M;
    p[i]=p[i-1]*p1%M;
    }
for(i=0;i<l2-l1+1;i++)
    {j=i+l1-1;
    x=((h[j+1]-h[i]*p[j-i+1])%M+M)%M;
    if(x==h2) sol[++q]=i;
    }
    g<<q<<'\n';
    if(q>1000)
        q=1000;
    for(i=1;i<=q;i++)
        g<<sol[i]<<" ";

}