Cod sursa(job #2736000)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 3 aprilie 2021 02:20:24
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int p1 = 666013;
const int p2 = 100007;
vector <int> sol;
string A, B;

int lgput1(int a, int b)
{
    if(b == 0)
        return 1;
    int p = lgput1(a, b / 2);
    if(b % 2 == 0)
        return p * p % p1;
    return (p * p % p1) * a % p1;
}

int lgput2(int a, int b)
{
    if(b == 0)
        return 1;
    int p = lgput2(a, b / 2);
    if(b % 2 == 0)
        return p * p % p2;
    return (p * p % p1) * a % p2;
}


int main()
{
    in >> A >> B;
    int n = A.size();
    int m = B.size();
    int hshA1 = 0;
    int hshA2 = 0;
    for(int i = 0; i < n; i++)
    {
        hshA1 = 26LL * hshA1 + A[i] % p1;
        hshA2 = 26LL * hshA2 + A[i] % p2;
    }
    //cerr << hshA1 << " " << hshA2 << "\n";
    long long act1 = 0;
    long long act2 = 0;
    for(int i = 0; i < min(n - 1, m); i++)
    {
        act1 = 26LL * act1 + B[i] % p1;
        act2 = 26LL * act2 + B[i] % p2;
    }
    for(int i = n - 1; i < m; i++)
    {
        act1 = (26LL * act1 + B[i]) % p1;
        act2 = (26LL * act2 + B[i]) % p2;
        //cerr << act1 << " " << act2 << "\n";
        if(act1 == hshA1 && act2 == hshA2)
            sol.push_back(i - n + 1);
        act1 = (act1 - lgput1(26, n - 1) * B[i - n + 1] + p1) % p1;
        act2 = (act2 - lgput2(26, n - 1) * B[i - n + 1] + p2) % p2;
    }
    out << sol.size() << "\n";
    for(int i = 0; i < min(1000, (int)sol.size()); i++)
        out << sol[i] << " ";
    out << "\n";
    return 0;
}