Cod sursa(job #3358882)

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

using namespace std;

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

const int MOD = 1000000007;
vector<int> pozitii;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    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 * 97) % MOD;
    }

    for(int i = 0; i < lenA; i++)
    {
        hashA = (hashA * 97 + A[i]) % MOD;
        hashB = (hashB * 97 + 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 * 97 + 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";
    if(pozitii.size() < 1000)
    {
        for(auto nr : pozitii)
        {
            fout << nr << " ";
        }
        fout << "\n";
    }
    else
    {
        for(int i = 0; i < 1000; i++)
        {
            fout << pozitii[i] << " ";
        }
        fout << "\n";
    }
    
    return 0;
}