Cod sursa(job #2882155)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 31 martie 2022 10:54:40
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
//Ilie Dumitru
#include<cstdio>
#include<cstring>
typedef long long int ll;
const int NMAX=2000005;

char pattern[NMAX], text[NMAX];
int N/*pattern*/, M/*text*/;
int pi[NMAX];
int nrAp, ans[1000];

void prefix()
{
    int i, k;
    pi[0]=0;
    pi[1]=0;
    for(i=2, k=0;i<=N;++i)
    {
        while(k && pattern[k]!=pattern[i-1])
            k=pi[k];
        if(pattern[k]==pattern[i-1])
            pi[i]=++k;
    }
    //for(i=0;i<N;++i)
    //    printf("%c %d\n", pattern[i], pi[i+1]);
}

void match()
{
    int q, i;
    for(q=0, i=0;i<M;++i)
    {
        while(q && pattern[q]!=text[i])
            q=pi[q];
        if(pattern[q]==text[i])
            ++q;
        if(q==N)
        {
            if(nrAp<1000)
                ans[nrAp]=i-N+1;
            ++nrAp;
        }
    }
}

int main()
{
    int i;
    FILE* f=fopen("strmatch.in", "r"), *g=fopen("strmatch.out", "w");

    fgets(pattern, NMAX, f);
    fgets(text, NMAX, f);
    N=strlen(pattern);
    if(pattern[N-1]=='\n')
        pattern[--N]=0;
    M=strlen(text);
    if(text[M-1]=='\n')
        text[--M]=0;
    prefix();
    match();
    fprintf(g, "%d\n", nrAp);
    for(i=0;i<nrAp && i<1000;++i)
        fprintf(g, "%d ", ans[i]);
    fclose(f);
    fclose(g);
    return 0;
}