Cod sursa(job #3249974)

Utilizator Ruxandra009Ruxandra Vasilescu Ruxandra009 Data 18 octombrie 2024 22:29:52
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.86 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]; long long numi;
vector<int> v;

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

long long expo(long long a, long long b, long long t)
{
    long long sol = 1;
    while(b)
        if(b % 2 == 0){
            if(t == 1)
                a = (1LL * a * a) % mod1;
            else
                a = (1LL * a * a) % mod2;

            b /= 2;
        }

        else{
            if(t == 1)
                sol = (1LL * sol * a) % mod1;
            else
                sol = (1LL * sol * a) % mod2;

            b --;
        }

    return sol;
}

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;
    }

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

        if(i >= n)
            nr1 = (nr1 - 1LL * codif(b[i - n]) * expo(b1, n, 1) + 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]) * expo(b1, n, 2) + mod2) % mod2;

        nr2 %= mod2;

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

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