Cod sursa(job #2869964)

Utilizator CristianPavelCristian Pavel CristianPavel Data 11 martie 2022 22:49:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <cstring>
#define Mod1 666013
#define Mod2 10007
#define maxN 2000001
#define Baza 256
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");

char s1[maxN], s2[maxN];
int Nr = 0;
int Poz[maxN];

void rabin_karp(char s1[], char s2[])
{
    int l1 = strlen(s1), l2 = strlen(s2);
    int Putere1 = 1, Putere2 = 1;
    int h1 = 0, h2 = 0, h3 = 0, h4 = 0;
    for(int i = 0; i < l1; i++)
    {
        if(i != 1){
            Putere1 = (Putere1 * Baza) % Mod1;
            Putere2 = (Putere2 * Baza) % Mod2;
        }
        h1 = (h1 * Baza + s1[i]) % Mod1;
        h2 = (h2 * Baza + s1[i]) % Mod2;
        h3 = (h3 * Baza + s2[i]) % Mod1;
        h4 = (h4 * Baza + s2[i]) % Mod2;
    }
    for(int i = 0; i <= l2 - l1; i++)
    {
        if(h1 == h3 && h2 == h4){
            Nr++;
            Poz[Nr] = i;
        }
        h3 = ((h3 - (s2[i] * Putere1) % Mod1 + Mod1) * Baza + s2[i + l1]) % Mod1;
        h4 = ((h4 - (s2[i] * Putere2) % Mod2 + Mod2) * Baza + s2[i + l1]) % Mod2;
    }
}
int main()
{
    cin.get(s1, maxN);
    cin.get();
    cin.get(s2, maxN);
    rabin_karp(s1,s2);
    cout<<Nr<<"\n";
    for(int i = 1; i <= Nr && i<=1000; i++)
        cout << Poz[i] << " ";
    cin.close();
    cout.close();
    return 0;

}