Cod sursa(job #2233793)

Utilizator PopeangaMihneaPopeanga Mihnea- Stefan PopeangaMihnea Data 24 august 2018 15:03:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <bits/stdc++.h>

using namespace std;

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

const int LONG=2000000;
const int MOD1=100007;
const int MOD2=100021;
const int P=73;
char pattern[LONG+1];
char text[LONG+1];
int sol[LONG+1];
int hash_txt1, hash_txt2,
    hash_pat1, hash_pat2;


int main()
{
    fin.getline(pattern, LONG+1);
    fin.getline(text, LONG+1);
    int N=strlen(text);
    int M=strlen(pattern);
    if(M>N)
    {
        fout<<"0\n";
        return 0;
    }
    int aux1=1, aux2=1;
    for(int i=0; i<M; ++i)
    {
        hash_pat1=(hash_pat1*P+pattern[i])%MOD1;
        hash_pat2=(hash_pat2*P+pattern[i])%MOD2;
        hash_txt1=(hash_txt1*P+text[i])%MOD1;
        hash_txt2=(hash_txt2*P+text[i])%MOD2;
        if(i!=M-1)
        {
            aux1=(aux1*P)%MOD1;
            aux2=(aux2*P)%MOD2;
        }
    }
    int k=0;
    if(hash_txt1==hash_pat1 && hash_txt2==hash_pat2)
        sol[++k]=0;
    for(int i=M; i<N; ++i)
    {
        hash_txt1=(P*(hash_txt1-(text[i-M]*aux1)%MOD1+MOD1)+text[i])%MOD1;
        hash_txt2=(P*(hash_txt2-(text[i-M]*aux2)%MOD2+MOD2)+text[i])%MOD2;
        if(hash_txt1==hash_pat1 && hash_txt2==hash_pat2)
            sol[++k]=i-M+1;
    }
    fout<<k<<"\n";
    for(int i=1; i<=k && i<=1000; ++i) fout<<sol[i]<<" ";
    fout<<"\n";
    return 0;
}