Cod sursa(job #3333519)

Utilizator parrot279Sofi Tudose parrot279 Data 13 ianuarie 2026 20:16:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int mod = 1e9+7, p = 65;
string a, b;
int n, m, cnt;
vector<int> poz(1002);
long long pattern, secv, pw = 1;

int main()
{
    fin>>a>>b;
    n = a.size();
    m = b.size();
    for(int i = 0; i < n; ++i)
    {
        pattern = (pattern * p + a[i]) % mod;
        secv = (secv * p + b[i]) % mod;
        if(i < n-1)
            pw = pw * p % mod;
    }
    if(pattern == secv)
    {
        ++cnt;
        poz[cnt] = 0;
    }
    for(int i = n; i < m; ++i)
    {
        int st = i - n + 1;
        secv = (secv - (b[st-1] * pw % mod) + mod) % mod;
        secv = (secv * p + b[i]) % mod;
        if(secv == pattern)
        {
            ++cnt;
            if(cnt <= 1000)
                poz[cnt] = st;
        }
    }
    fout<<cnt<<'\n';
    for(int i = 1; i <= cnt && i <= 1000; ++i)
        fout<<poz[i]<<' ';


    return 0;
}