Cod sursa(job #2439968)

Utilizator DavidLDavid Lauran DavidL Data 17 iulie 2019 12:17:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.12 kb
#include <bits/stdc++.h>
using namespace std;

#define cin fi
#define cout fo
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");

const int NMAX = 2e6 + 5;
const int MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 9;
const int baza = 62;

int n, m;
char A[NMAX], B[NMAX];
vector <int> rez;
int total;

inline int getMod(long long x, int M)
{
    return x - x / M * M;
}

char cod(char x)
{
    if ('a' <= x && x <= 'z')
        return x - 'a';
    else if ('A' <= x && x <= 'Z')
        return x - 'A' + ('z' - 'a') + 1;
    else if ('0' <= x && x <= '9')
        return x - '0' + ('Z' - 'A' + ('z' - 'a') + 1) + 1;
}

int main()
{
    cin >> A + 1 >> B + 1;
    m = strlen(A + 1);
    n = strlen(B + 1);

    for (int i = 1; i <= m; i++)
        A[i] = cod(A[i]);
    for (int i = 1; i <= n; i++)
        B[i] = cod(B[i]);

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

    long long maska1 = 0, maska2 = 0;
    long long maskb1 = 0, maskb2 = 0;
    for (int i = 1; i <= m; i++)
    {
        maska1 = getMod(maska1 * baza + A[i], MOD1);
        maska2 = getMod(maska2 * baza + A[i], MOD2); 
        maskb1 = getMod(maskb1 * baza + B[i], MOD1);
        maskb2 = getMod(maskb2 * baza + B[i], MOD2); 
    }

    long long p1 = 1, p2 = 1;
    for (int i = 1; i < m; i++)
    {
        p1 = getMod(p1 * baza, MOD1);
        p2 = getMod(p2 * baza, MOD2);
    }

    if (maska1 == maskb1 && maska2 == maskb2)
        total++, rez.push_back(1);

    for (int i = m + 1; i <= n; i++)
    {
        maskb1 = (maskb1 - p1 * B[i - m]);
        while (maskb1 < 0)
            maskb1 += MOD1;

        maskb2 = (maskb2 - p2 * B[i - m]);
        while (maskb2 < 0)
            maskb2 += MOD2;

        maskb1 = getMod(maskb1 * baza + B[i], MOD1);
        maskb2 = getMod(maskb2 * baza + B[i], MOD2);

        if (maskb1 == maska1 && maskb2 == maska2)
        {
            total++;
            if (rez.size() < 1000)
                rez.push_back(i - m + 1);
        }
    }

    cout << total << "\n";
    for (auto x: rez)
        cout << x - 1 << " ";

    return 0;
}