Cod sursa(job #2570907)

Utilizator XXMihaiXX969Gherghinescu Mihai Andrei XXMihaiXX969 Data 4 martie 2020 19:55:55
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda r3capitusulare Marime 1.79 kb
#include <bits/stdc++.h>

using namespace std;

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

const int h = 71;
const int mod1 = 367;
const int mod2 = 251;
const int DIM = 2e6 + 7;

string a;
string b;

int pw1[DIM];
int pw2[DIM];

vector <int> rez;

int main()
{
   in >> a;
   in >> b;

   int cnt = 0;

   pw1[0] = 1;
   pw2[0] = 1;

   int n = a.size();
   int m = b.size();

   if(n > m)
   {
       out << 0;
       return 0;
   }

   for(int i = 1; i < n; i++)
   {
    pw1[i] = (1ll * pw1[i - 1] * h) % mod1;
    pw2[i] = (1ll * pw2[i - 1] * h) % mod2;
   }

   int Sm1 = 0;
   int Sm2 = 0;

   for(int i = 0; i < n; i++)
   {
    int nr = a[i] - '0';

    Sm1 = (1ll * Sm1 + (1ll * nr * pw1[n - i - 1]) % mod1) % mod1;
    Sm2 = (1ll * Sm2 + (1ll * nr * pw2[n - i - 1]) % mod2) % mod2;

   }

   int Sc1 = 0;
   int Sc2 = 0;

   for(int i = 0; i < n; i++)
   {
    int nr = b[i] - '0';

    Sc1 = (1ll * Sc1 + (1ll * nr * pw1[n - i - 1]) % mod1) % mod1;
    Sc2 = (1ll * Sc2 + (1ll * nr * pw2[n - i - 1]) % mod2) % mod2;

   }
   if(Sc1 == Sm1 && Sc2 == Sm2)
       {
           cnt++;
           rez.push_back(0);
       }


   for(int i = n; i < m; i++)
   {
       int nr1 = b[i - n] - '0';
       int nr2 = b[i] - '0';

        Sc1 = ((((1ll * Sc1 - (1ll * pw1[n - 1] * nr1) % mod1 + mod1) % mod1 ) * h) % mod1 + nr2) % mod1;
        Sc2 = ((((1ll * Sc2 - (1ll * pw2[n - 1] * nr1) % mod2 + mod2) % mod2 ) * h) % mod2 + nr2) % mod2;

        if(Sc1 == Sm1 && Sc2 == Sm2)
            {
                cnt++;
                if(cnt <= 1000)
                rez.push_back(i - n + 1);
            }

   }

    out << cnt<<'\n';

    for(int i = 0; i < rez.size(); i++)
        out << rez[i]<<" ";


    return 0;
}