Cod sursa(job #2419058)

Utilizator TudorChirila11Tudor Chirila TudorChirila11 Data 7 mai 2019 17:02:00
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>
#define MOD1 1000000007
#define MOD2 9613
#define baza 31
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n, m, i, j, b, h[2000005];
int x, y, v1, nr, k;
string s1, s2;
int main()
{
    fin>>s1>>s2;
    n=s1.size();
    m=s2.size();
    b=1;
    for(i=n-1;i>=0;i--)
        {
            v1=(v1+s1[i]*b)%MOD1;
            nr=(nr+s2[i]*b)%MOD1;
            b=(b*baza)%MOD1;
        }
   // fout<<nr<<' ';
   if(nr==v1)
   {
       k++;
       h[k]=0;
   }
    for(i=n;i<m;i++)
    {
        nr=(((nr*baza)%MOD1-(s2[i-n]*b)%MOD1)%MOD1+s2[i])%MOD1;
        nr=(nr+MOD1)%MOD1;
        if(nr==v1)
        {
            k++;
            h[k]=i-n+1;
        }
       // fout<<nr<<' ';
        //h[nr].push_back(i-n+1);
    }
    int sz=k;
    fout<<sz<<'\n';
    sz=min(sz,1000);
    for(i=1;i<=sz;i++)
        fout<<h[i]<<' ';
    fout<<'\n';
    return 0;
}