Cod sursa(job #3171654)

Utilizator Bolfa_DBolfa Diana Bolfa_D Data 19 noiembrie 2023 12:06:09
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char a[2000200], b[2000200];
long long nr,nr1;
int fr, ans[2000200];
int main()
{

    fin.getline(a,2000200);
    fin.getline(b,2000200);
    long long exp=1;
    int n=strlen(a), m=strlen(b);

    for(int i=0;i<n;++i)
    {
        nr=(nr*26+b[i]-'A'+1)%mod;
        nr1=(nr1*26+a[i]-'A'+1)%mod;
        exp=exp*26%mod;
    }
    exp=exp/26;

    if(nr1==nr)
    {
        ++fr;
        ans[fr]=0;
    }

    for(int i=n;i<m;++i)
    {
        nr=((nr-exp*(b[i-n]-'A'+1))*26+b[i]-'A'+1)%mod;
        if(nr<0)
            nr=nr+mod;
        if(nr==nr1)
        {
            ++fr;
            ans[fr]=i-n+1;
        }
    }

    fout<<fr<<'\n';
    for(int i=1;i<=fr;++i)
        fout<<ans[i]<<" ";

    return 0;
}