Cod sursa(job #3249980)

Utilizator Ruxandra009Ruxandra Vasilescu Ruxandra009 Data 18 octombrie 2024 22:45:26
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

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

const long long nmax = 2000005;
const long long b1 = 131;
const long long mod1 = 1e9 + 7, mod2 = 1e9 + 9;
char a[nmax], b[nmax];
vector<int> v; long long exp1 = 1, exp2 = 1;

long long codif(char a){
    return a - '0' + 1;
}

int main()
{
    f >> a >> b;
    long long num1 = 0, num2 = 0;
    for(long long i = 0; a[i]; i ++)
    {
        num1 = (1LL * num1 * b1) % mod1;
        num1 = (num1 + codif(a[i])) % mod1;

        num2 = (1LL * num2 * b1) % mod2;
        num2 = (num2 + codif(a[i])) % mod2;

        exp1 = (1LL * exp1 * b1) % mod1;
        exp2 = (1LL * exp2 * b1) % mod2;
    }

    long long nr1 = 0, nr2 = 0, n = strlen(a);
    for(long long i = 0; b[i] && v.size() < 1000; i ++)
    {
        nr1 = (1LL * nr1 * b1) % mod1;
        nr1 = (nr1 + codif(b[i])) % mod1;

        if(i >= n)
            nr1 = (nr1 - 1LL * codif(b[i - n]) * exp1 % mod1 + mod1) % mod1;

        nr1 %= mod1;

        nr2 = (1LL * nr2 * b1) % mod2;
        nr2 = (nr2 + codif(b[i])) % mod2;

        if(i >= n)
            nr2 = (nr2 - 1LL * codif(b[i - n]) * exp2 % mod2 + mod2) % mod2;

        nr2 %= mod2;

        if(nr1 == num1 && nr2 == num2 && v.size() < 1000)
            v.push_back(i - n + 1);
    }

    g << v.size() << '\n';
    for(int i = 0; i < v.size(); i ++)
        g << v[i] << " ";
    return 0;
}