Cod sursa(job #2865078)

Utilizator CristianPavelCristian Pavel CristianPavel Data 8 martie 2022 14:43:45
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char s1[2000001];
char s2[2000001];
int v[2000001];
int nr=0;
void rabin_karp(char s1[], char s2[])
{
    int h1=0,h2=0,l1=strlen(s1), l2=strlen(s2);
    int putere=1;
    int baza=256;
    int mod=1007;
    bool ok;
    for(int i=0;i<l1;i++)
    {
        if(i!=1) putere=(putere*baza)%mod;
        h1=((h1*baza)+s1[i])%mod;
        h2=((h2*baza)+s2[i])%mod;
    }
    for(int i=0;i<=l2-l1;i++)
    {
        if(h1==h2){
            ok=true;
            for(int j=0;j<l1;j++)
                if(s1[j]!=s2[j+i]){
                    ok=false;
                    break;
                }
            if(ok){
                nr++;
                v[i]=1;
            }
        }
        else{
            h2=((h2-s2[i]*putere)*baza + s2[i+l1])%mod;
            if(h2<0) h2=h2+mod;
        }
    }
}
int main()
{
    cin.get(s1,100);
    cin.get();
    cin.get(s2,100);
    rabin_karp(s1,s2);
    cout<<nr<<" "<<endl;
    nr=0;
    for(int i=0;i<=strlen(s2) && nr<1000;i++)
    {
        if(v[i]) cout<<i<<" ";
        nr++;
    }
    cin.close();
    cout.close();
    return 0;
}