Cod sursa(job #2419137)

Utilizator Catalin_GriuGriu Catalin Catalin_Griu Data 7 mai 2019 18:24:56
Problema Potrivirea sirurilor Scor 78
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define MOD 1000000007
#define LMAX 2000003
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

string str1;
string str2;

long long k, h1, h2,b, r, n,m,i;
int rs[LMAX];

int main()
{
    fin>>str1>>str2;
    n = str1.size();
    m = str2.size();
    b=1;
    for(i=n-1;i>=0; i--)
    {
        k=(k+(str1[i])*b%MOD+MOD)%MOD;
        h1+=((str2[i])*b%MOD+MOD)%MOD;
        b=(b*31+MOD)%MOD;
    }

    if(k==h1)
        rs[r++]=0;

    for(i=n; i<m; i++)
    {
        //h2=((h1*31)%MOD-((str2[st-1]-'A')*pow(31, lp))%MOD+str2[dr]-'A')%MOD;
        h1=(((h1*31+MOD)%MOD-((str2[i-n])*b+MOD)%MOD+MOD)%MOD+str2[i]+MOD)%MOD;
        h1=(h1+MOD)%MOD;

        if(k==h1)
            rs[r++]=i-n+1;
    }

    int rr = min(r,1LL*1000);
    fout<<r<<'\n';
    for(i=0; i<rr; i++)
        fout<<rs[i]<<' ';

    return 0;
}