Cod sursa(job #2339090)

Utilizator petru.ciocirlanPetru Ciocirlan petru.ciocirlan Data 8 februarie 2019 12:57:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
using namespace std;

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

const int MAXLEN = 2000000 + 16;
const int MAXSOL = 1000 + 16;
char Pattern[MAXLEN], Text[MAXLEN];
int Sol[MAXSOL], PSfix[MAXLEN];
int N, M, Count;

int main()
{
    fin >> (Pattern+1);
    fin >> (Text+1);

    int K;
    /// Precalculare prefix/sufix KMP
    PSfix[1] = 0;
    for(N = 2; Pattern[N]; ++N)
    {
        K = PSfix[N-1];
        while(K > 0 && Pattern[K+1] != Pattern[N])
            K = PSfix[K];
        if(Pattern[K+1] == Pattern[N])
            ++K;
        PSfix[N] = K;
    }
    --N;

    K = 0;
    for(M = 1; Text[M]; ++M)
    {
        while(K > 0 && Pattern[K+1] != Text[M])
            K = PSfix[K];
        if(Pattern[K+1] == Text[M])
            ++K;
        if(K == N)
        {
            ++Count;
            if(Count <= 1000)
                Sol[Count] = M - N;
            K = PSfix[K];
        }
    }
    --M;

    fout << Count << '\n';
    if(Count > 1000)
        Count = 1000;
    for(int i = 1; i <= Count; ++i)
        fout << Sol[i] << ' ';

    return 0;
}