Cod sursa(job #3041261)

Utilizator AndreiBOTOBotocan Andrei AndreiBOTO Data 31 martie 2023 10:48:47
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>

///#include <tryhardmode>
///#include <GODMODE::ON>

using namespace std;

//#define cin fin
//#define cout fout

ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

const int BASE=27;
const int MOD1=100007;
const int MOD2=100021;

vector<int>v;
string a;
string b;

int lgput(int a,int b,int MODU)
{
    int total;
    if(b==0)
        return 1;
    else
    {
        if(b%2==0)
        {
            total=lgput(a,b/2,MODU)%MODU;
            total=1LL*total*total%MODU;
            return total;
        }
        else
        {
            total=lgput(a,b/2,MODU)%MODU;
            total=1LL*total*total%MODU;
            return 1LL*total*a%MODU;
        }
    }
}

void rabin(int n,int m)
{
    int i,j,hash1a=0,hash1b=0,hash2a=0,hash2b=0,p1,p2;
    for(i=0;i<n;i++)
    {
        hash1a=(hash1a*BASE+(a[i]-'0'))%MOD1;
        hash2a=(hash2a*BASE+(a[i]-'0'))%MOD2;
        hash1b=(hash1b*BASE+(b[i]-'0'))%MOD1;
        hash2b=(hash2b*BASE+(b[i]-'0'))%MOD2;
    }
    if(hash1a==hash1b && hash2a==hash2b)
        v.push_back(0);
    p1=lgput(BASE,n-1,MOD1);
    p2=lgput(BASE,n-1,MOD2);
    for(i=n;i<=m;i++)
    {
        hash1b=((hash1b-((b[i-n]-'0')*p1)%MOD1+MOD1)*BASE+(b[i]-'0'))%MOD1;
        hash2b=((hash2b-((b[i-n]-'0')*p2)%MOD2+MOD2)*BASE+(b[i]-'0'))%MOD2;
        if(hash1a==hash1b && hash2a==hash2b)
            v.push_back(i-n+1);
    }
}

int main()
{
    int i,j,n,m,debuff=0;
    cin>>a>>b;
    n=a.size();
    m=b.size();
    rabin(n,m);
    cout<<v.size()<<"\n";
    for(auto i:v)
    {
        debuff++;
        cout<<i<<" ";
        if(debuff==1000)
            exit(0);
    }
    return 0;
}