Cod sursa(job #2442504)

Utilizator gavra_bogdanBogdan Gavra gavra_bogdan Data 24 iulie 2019 11:00:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>
using namespace std;
const long long mod1=1e9+7;
const long long mod2=666013;
vector<long long>v;
int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    string a,b;
    cin>>a>>b;
    long long p1=0,p2=0,pb1=0,pb2=0,la=a.size(),p1001=1,p1002=1;
    for(long long i=1;i<la;i++)
        p1001=((long long)p1001*100)%mod1;
    for(long long i=1;i<la;i++)
        p1002=((long long)p1002*100)%mod2;
    for(long long i=0;i<a.size();i++)
    {
        p1=((long long)p1*100+(a[i]-'0'))%mod1;
        p2=((long long)p2*100+(a[i]-'0'))%mod2;
    }
    for(long long i=0;i<la;i++)
    {
        pb1=((long long)pb1*100+(b[i]-'0'))%mod1;
        pb2=((long long)pb2*100+(b[i]-'0'))%mod2;
    }
    if(p1==pb1 and p2==pb2)
        v.push_back(0);
    for(long long i=la;i<b.size();i++)
    {
        pb1=(((long long)pb1-(b[i-la]-'0')*p1001)%mod1+mod1)%mod1;
        pb1=((long long)pb1*100+(b[i]-'0')+2*mod1)%mod1;
        pb2=(((long long)pb2-(b[i-la]-'0')*p1002)%mod2+mod2)%mod2;
        pb2=((long long)pb2*100+(b[i]-'0')+2*mod2)%mod2;
        if(p1==pb1 and p2==pb2)
            v.push_back(i-la+1);
    }
    cout<<v.size()<<"\n";
    for(long long i=0;i<min(1000,(int)v.size());i++)
        cout<<v[i]<<" ";
    return 0;
}