Cod sursa(job #2736432)

Utilizator MohneaGosuMihnea Gusu MohneaGosu Data 3 aprilie 2021 14:35:50
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
const int baza=123;
const int mod1=100007;
const int mod2=100021;
char A[2000001];
char B[2000001];
vector <int> v;
int main()
{
    cin>>A;
    cin>>B;
    int n=0,n1=strlen(B);
    int m=strlen(A);
    int put1=1;
    int put2=1;
    int rmod1=0,rmod2=0,bmod1=0,bmod2=0;
    int i,c,c1;
    for (i=0;i<m && i<n1;i++){
        c=A[i];
        rmod1=(1LL*rmod1*baza+c)%mod1;
        rmod2=(1LL*rmod2*baza+c)%mod2;

        c=B[i];
        bmod1=(1LL*bmod1*baza+c)%mod1;
        bmod2=(1LL*bmod2*baza+c)%mod2;

        put1=(1LL*put1*baza)%mod1;
        put2=(1LL*put2*baza)%mod2;
    }
    if (m>n1){
        cout<<0;
        return 0;

    }
    if (rmod1==bmod1 && rmod2==bmod2){
        v.push_back(0);///i-m+1;
        n++;
    }
    for (;B[i];i++){
        c=B[i];

        c1=B[i-m];

        bmod1=(1LL*(bmod1-(put1*c1)%mod1+mod1)*baza+c)%mod1;///+mod1 ca sa fie pozitiv
        bmod2=(1LL*(bmod2-(put2*c1)%mod2+mod2)*baza+c)%mod2;
        if (rmod1==bmod1 && rmod2==bmod2 && n<1000) v.push_back(i-m+1),n++;
    }
    cout<<n<<"\n";
    for (i=0;i<n;i++){
        cout<<v[i]<<" ";
    }
    return 0;
}