Cod sursa(job #3300530)

Utilizator raileanu-alin-gabrielRaileanu Alin-Gabriel raileanu-alin-gabriel Data 16 iunie 2025 22:19:00
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#define int long long

using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

const int q=1e9+7;
const int B=263;
const int NMAX=2*1e6+5;

char p[NMAX], t[NMAX];
int ans[1005];

bool check(int poz)
{
    int i;
    for(i=0; p[i]; i++)
    {
        if(p[i]!=t[i+poz]) return false;
    }
    return true;
}

signed main()
{
    cin>>p;
    cin>>t;
    int i, hshp=0, pw=1, hsht=0;
    for(i=0; p[i]; i++)
    {
        hshp=(hshp*B+p[i])%q;
        if(p[i+1]) pw=(pw*B)%q;
        hsht=(hsht*B+t[i])%q;
    }
    int m=i, cnt=0;
    for(i=0; t[i+m-1]; i++)
    {
        if(hsht==hshp)
        {
            if(check(i))
            {
                cnt++;
                if(cnt<=1000) ans[cnt]=i;
            }
        }
        hsht=((hsht+q-t[i]*pw)*B+t[i+m])%q;
    }
    cout<<cnt<<'\n';
    for(i=1; i<=min(cnt, 1LL*1000); i++) cout<<ans[i]<<' ';
    return 0;
}