Cod sursa(job #2734923)

Utilizator MohneaGosuMihnea Gusu MohneaGosu Data 1 aprilie 2021 17:19:10
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
const int baza=56;///daca e litere mari si mici 28 daca e doar mici
const int mod1=1000000007;
const int mod2=666013;
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++){
        if (A[i]>='a' && A[i]<='z') c=A[i]-'a'+1;
        else c=A[i]-'A'+28;
        rmod1=(rmod1*baza+c)%mod1;
        rmod2=(rmod2*baza+c)%mod2;

        if (B[i]>='a' && B[i]<='z') c=B[i]-'a'+1;
        else c=B[i]-'A'+28;
        bmod1=(bmod1*baza+c)%mod1;
        bmod2=(bmod2*baza+c)%mod2;

        put1=(put1*baza)%mod1;
        put2=(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++){
        if (B[i]>='a' && B[i]<='z') c=B[i]-'a'+1;
        else c=B[i]-'A'+28;

        if (B[i-m]>='a' && B[i-m]<='z') c1=B[i-m]-'a'+1;
        else c1=B[i-m]-'A'+28;

        bmod1=(((bmod1-((put1*c1)%mod1)+mod1)*baza+c)%mod1)%mod1;///+mod1 ca sa fie pozitiv
        bmod2=(((bmod2-((put2*c1)%mod2)+mod2)*baza+c)%mod2)%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;
}