Cod sursa(job #2734049)

Utilizator MohneaGosuMihnea Gusu MohneaGosu Data 31 martie 2021 12:15:51
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.81 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;
int maxput1 (int p)
{
    long long a=baza,s=1;
    int i;
    for (i=0;(1<<i)<=p;i++){
        if (((1<<i)&p)!=0) s=(s*a)%mod1;
        a=(a*a)%mod1;
    }
    return s%mod1;
}
int maxput2 (int p)
{
    long long a=baza,s=1;
    int i;
    for (i=0;(1<<i)<=p;i++){
        if (((1<<i)&p)!=0) s=(s*a)%mod2;
        a=(a*a)%mod2;
    }
    return s%mod2;
}
char A[2000001];
char B[2000001];
vector <int> v;
int main()
{
    cin>>A;
    cin>>B;
    int n=0;
    int m=strlen(A);
    int put1=maxput1(m-1);
    int put2=maxput2(m-1);
    int rmod1=0,rmod2=0,bmod1=0,bmod2=0;
    int i,c,c1;
    for (i=0;i<m;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;
    }
    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))*baza+c)%mod1 +mod1)%mod1;///+mod1 ca sa fie pozitiv
        bmod2=(((bmod2-((put2*c1)%mod2))*baza+c)%mod2 +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;
}