Cod sursa(job #2897544)

Utilizator BuzatuCalinBuzatu Calin BuzatuCalin Data 3 mai 2022 23:42:15
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
#define DIM 2000001
int m,n,t,p,rasp[DIM],r;
char P[DIM],T[DIM];
void potrivire_rabin_karp(int d,int q){
    int h=1;
    for(int i=0;i<m-1;i++){
        h=(d*h)%q;
    }
    h%=q;
    p=0;int tempT;
    for(int i=0;i<m;i++){
        p=(d*p+(int)P[i])%q;
        tempT=((d*t)+(int)T[i]);
        t=tempT%q;
    }
    for(int s=0;s<=n-m;s++){
        if(p==t){
            bool ok=true;
            for(int j=0;j<m;j++)
            {
                if(P[j]!=T[s+j]){
                    ok=false;
                    break;
                }
            }
            if(ok && r<1000){
                rasp[r]=s;
                r++;
            }
        }
        tempT=((d*(t-T[s]*h)+(int)T[s+m]));
        t=tempT%q;
        if(t<0){
            t+=q;
        }
    }
}
int main(){
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    fin>>P>>T; 
    m=strlen(P);
    n=strlen(T);
    potrivire_rabin_karp(1000000,31);
    fout<<r<<'\n';
    for(int i=0;i<r;i++){
        fout<<rasp[i]<<' ';
    }
}