Cod sursa(job #2233791)

Utilizator PopeangaMihneaPopeanga Mihnea- Stefan PopeangaMihnea Data 24 august 2018 14:40:43
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>

using namespace std;

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

const int LONG=2000000;
const int MOD=666013;
const int P=73;
char pattern[LONG+1];
char text[LONG+1];
int sol[LONG+1];


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 aux=1, pat=0, txt=0;
    for(int i=0; i<M-1; ++i)
        aux=(aux*P)%MOD;
    for(int i=0; i<M; ++i)
    {
        pat=(P*pat+pattern[i])%MOD;
        txt=(P*txt+text[i])%MOD;
    }
    int k=0;
    for(int i=0; i<=N-M; ++i)
    {
        if(pat==txt)
        {
            bool ok=1;
            for(int j=0; j<M && ok; ++j)
                if(text[i+j]!=pattern[j]) ok=0;
            if(ok) sol[++k]=i;
        }
        if(i<N-M)
        {
            txt=(P*(txt-text[i]*aux)+text[i+M])%MOD;
            if(text<0) txt=txt+MOD;
        }
    }
    fout<<k<<"\n";
    for(int i=1; i<=k && i<=1000; ++i) fout<<sol[i]<<" ";
    fout<<"\n";
    return 0;
}