Cod sursa(job #2196952)

Utilizator danielsociuSociu Daniel danielsociu Data 20 aprilie 2018 19:19:50
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
#define NMAX 20000000
#define MOD 10007
char A[NMAX],B[NMAX];
int NA, NB, hashA=0, hashB=0,P=73, PA=1, SOL[NMAX], k=0;

int main()
{
    cin>>A;
    cin>>B;
    NA=strlen(A);
    NB=strlen(B);
    if(NA>NB){
        cout<<0;
        return 0;
    }
    int xd=A[0];
    for(int i=0;i<NA;i++){
        hashA= (hashA*P + A[i])%MOD;
        if(i!=0)
            PA=(PA*P)%MOD;
    }
    for(int i=0;i<NA;i++){
        hashB= (hashB*P + B[i])%MOD;
    }
    if(hashA==hashB)
        SOL[++k]=0;
    for(int i=NA;i<NB;i++){
        hashB= (((hashB-(B[i-NA]*PA)%MOD)+MOD)*P + B[i])%MOD;
        if(hashA==hashB)
            SOL[++k]=i-NA+1;
    }
    cout<<k<<endl;
    for(int i=1;i<=k&&i<=1000;i++)
        cout<<SOL[i]<<' ';
}