Cod sursa(job #3293067)

Utilizator Tudor_CCTudor Cocu Tudor_CC Data 10 aprilie 2025 11:30:11
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>

using namespace std;

unsigned long long mod=1e9+7,b=31,p[2000005];

string s1,s2;

vector <int> v;

int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    p[0]=1;
    for(int i=1;i<=2000000;++i)
    {
        p[i]=(p[i-1]*b)%mod;
    }
    cin>>s1>>s2;
    unsigned long long n1=0,n2=0;
    for(int i=0;i<s1.size();++i)
    {
        n1=(n1*b+s1[i])%mod;
    }
    for(int i=0;i<s1.size();++i)
    {
        n2=(n2*b+s2[i])%mod;
    }
    if(n2==n1)
    {
        v.push_back(0);
    }
    for(int i=1;(i+s1.size()-1)<s2.size();++i)
    {
        int j=i+s1.size()-1;
        n2=(mod+n2-(1LL*s2[i-1]*p[s1.size()-1])%mod)%mod;
        n2=((1LL*n2*b)%mod+s2[j])%mod;
        if(n1==n2)
        {
            v.push_back(i);
        }
    }
    cout<<v.size()<<"\n";
    for(int i=0;i<v.size() && i<1000;++i)
    {
        cout<<v[i]<<" ";
    }
    return 0;
}