Cod sursa(job #3279842)

Utilizator Dragu_AndiDragu Andrei Dragu_Andi Data 24 februarie 2025 16:04:05
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int NMAX = 1000;
const int MOD=1e9 + 7, BASE=256;
int maxBaseInMod = 1;
int hashA = 0, curHashB = 0;
int a, b;
string A, B;
vector<int> matches;

void findie(int i)
{
    for(int j=0; j<a; j++)
        if(A[j]!=B[j+i])
            return;
    matches.push_back(i);
}

int main()
{
    fin >> A >> B;
    a=A.size();
    b=B.size();

    if (a > b)
    {
        fout << "0";
        return 0;
    }

    for (int i=1; i<a; i++)
        maxBaseInMod = (maxBaseInMod * BASE) % MOD;

    for(int i=0; i<a; i++)
    {
        curHashB = (curHashB * BASE + B[i]) % MOD;
        hashA = (hashA * BASE + A[i]) % MOD;
    }
    for(int i=a; i<=b; i++)
    {
        if(hashA == curHashB)
            findie(i-a);
        if(i<b)
        {
            curHashB = (curHashB + MOD - (maxBaseInMod * B[i - a]) % MOD) % MOD;
            curHashB = (curHashB * BASE + B[i]) % MOD;
        }
    }
    fout << matches.size() << '\n';
    int n=0;
    for(auto a: matches)
    {
        if(n>=1000)
            break;
        n++;
        fout << a << ' ';
    }
    return 0;
}