Cod sursa(job #3231656)

Utilizator Ruxandra009Ruxandra Vasilescu Ruxandra009 Data 27 mai 2024 15:42:38
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

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

const long long mod1 = 666013;
const long long mod2 = 10005;
const long long nmaxx = 2000005;

long long n, m, sumok1, sumok2, sumi1, sumi2;
char a[nmaxx], b[nmaxx];
vector<long long> v;

long long power(long long a, long long b, long long mod)
{
    long long sol = 1;
    while(b)
    {
        if(b % 2 == 0)
        {
            a = (1LL * a * a) % mod;
            b /= 2;
        }

        else
        {
            sol = (1LL * sol * a) % mod;
            b --;
        }
    }

    return sol;
}

int main()
{
    f >> a >> b;
    n = strlen(a);
    m = strlen(b);

    for(long long i = 0; i < n; i ++)
    {
        sumok1 = (sumok1 + (1LL * a[i] * power(127, n - i - 1, mod1)) % mod1) % mod1;
        sumok2 = (sumok2 + (1LL * a[i] * power(127, n - i - 1, mod2)) % mod2) % mod2;
    }

    for(long long i = 0; i < n; i ++)
    {
        sumi1 = (sumi1 + (1LL * b[i] * power(127, n - i - 1, mod1)) % mod1) % mod1;
        sumi2 = (sumi2 + (1LL * b[i] * power(127, n - i - 1, mod2)) % mod2) % mod2;
    }

    if(sumi1 == sumok1 && sumi2 == sumok2)
        v.push_back(0);

    for(long long i = n; i < m; i ++)
    {
        sumi1 = ((sumi1 - (b[i - n] * power(127, n - 1, mod1)) % mod1 + mod1) % mod1) * 127 + b[i];
        sumi1 %= mod1;

        sumi2 = ((sumi2 - (b[i - n] * power(127, n - 1, mod2)) % mod2 + mod2) % mod2) * 127 + b[i];
        sumi2 %= mod2;

        if(sumi1 == sumok1 && sumi2 == sumok2 && v.size() < 1000)
            v.push_back(i - n + 1);
    }

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