Cod sursa(job #3358878)

Utilizator adri22adria gram adri22 Data 21 iunie 2026 11:33:00
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MOD = 666013;
vector<int> pozitii;

int main()
{
    

    string A, B;
    fin >> A >> B;

    int lenA = A.length();
    int lenB = B.length();

    if(lenA > lenB)
    {
        fout << 0 << "\n";
        return 0;
    }

    long long hashA = 0;
    long long hashB = 0;
    long long P = 1;

    for(int i = 0; i < lenA - 1; i++)
    {
        P = (P * 37) % MOD;
    }

    for(int i = 0; i < lenA; i++)
    {
        hashA = (hashA * 37 + A[i]) % MOD;
        hashB = (hashB * 37 + B[i]) % MOD;
    }

    if(hashA == hashB)
    {
        if(B.compare(0, lenA, A) == 0)
        {
            pozitii.push_back(0);
        }
    }

    for(int i = lenA; i < lenB; i++)
    {
        long long scad = (B[i - lenA] * P) % MOD;
        hashB = hashB - scad;
        if(hashB < 0)
        {
            hashB += MOD;
        }
        
        hashB = (hashB * 37 + B[i]) % MOD;

        if(hashA == hashB)
        {
            int start_pos = i - lenA + 1;
            if(B.compare(start_pos, lenA, A) == 0)
            {
                pozitii.push_back(start_pos);
            }
        }
    }

    fout << pozitii.size() << "\n";

    for(auto nr : pozitii)
    {
        fout << nr << " ";
    }
    fout << "\n";
    
    return 0;
}