Cod sursa(job #2419047)

Utilizator TudorChirila11Tudor Chirila TudorChirila11 Data 7 mai 2019 16:47:53
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>
#define MOD1 65537
#define MOD2 9613
#define baza 31
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n, m, i, j, b;
int x, y, v1, nr;
vector <int> h[70000];
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<<' ';
    h[nr].push_back(0);
    for(i=n;i<m;i++)
    {
        nr=(((nr*baza)%MOD1-(s2[i-n]*b)%MOD1)%MOD1+s2[i])%MOD1;
        nr=(nr+MOD1)%MOD1;
       // fout<<nr<<' ';
        h[nr].push_back(i-n+1);
    }
    int sz=h[v1].size();
    fout<<sz<<'\n';
    sz=min(sz,1000);
    for(i=0;i<sz;i++)
        fout<<h[v1][i]<<' ';
    fout<<'\n';
    return 0;
}