Cod sursa(job #2470569)

Utilizator adiaioanaAdia R. adiaioana Data 9 octombrie 2019 15:02:03
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <cmath>
#include <cstring>
#define MOD1 1000000007
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int l1, l2, r,rm, rc, sol, v[2000100],P;
char sir1[2000100], sir2[2000100];

int ind(char ch);
int main()
{
    cin>>sir1;
    cin.get();
    cin>>sir2;
    l1=strlen(sir1);
    l2=strlen(sir2);

    rm=1;
    for(int i=0; i<l1; ++i)
    {
        rc=(rc*10+ind(sir1[i]))%MOD1;
        if(i)
        rm=(rm*10)%MOD1;
    }

    for(int i=0; i<l1; ++i)
        r=(r*10+ind(sir2[i]))%MOD1;

    if(r==rc)
        v[++sol]=0;
    P=pow(10,l1-1);
    for(int i=l1; i<l2; ++i)
    {
        r=(r+(MOD1-rm*ind(sir2[i-l1]))%MOD1)%MOD1;
        r=r *10 +ind(sir2[i]); r%=MOD1;

        if(r==rc)
            v[++sol]=i-l1+1;
    }

    cout<<sol<<'\n';
    for(int i=1; i<=min(sol,1000); ++i)
        cout<<v[i]<<' ';
    cout<<'\n';

    return 0;
}

int ind(char ch)
{
    if(ch>='a' && ch<='z')
        return 27+ch-'a';
    else return ch-'A'+1;
}