Cod sursa(job #2596990)

Utilizator k2e0e0w3qDumitrescu Gheorghe k2e0e0w3q Data 10 aprilie 2020 22:14:24
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <stdio.h>
#include <ctype.h>
#define N 2000001

char s[N], t[N];
int pi[N];
void compute () {
    int i=1, len=0;
    while (t[i])
        if (t[i]==t[len])
            pi[i++]=++len;
        else
            if (len)
                len=pi[len-1];
            else
                pi[i++]=0;
}

int main () {
    FILE *fin=fopen("strmatch.in", "r"),
         *fout=fopen("strmatch.out", "w");
    fgets(t, sizeof t, fin);
    fgets(s, sizeof s, fin);
    compute();

    fprintf (fout, "       \n");
    int i=0, j=0, ct=0;
    while (s[i]) {
        if (s[i]==t[j]) {
            ++i, ++j;
            if (!t[j]) {
                if (ct<1000)
                    fprintf (fout, "%d ", i-j);
                ct++;
                j=pi[j-1];
            }
        }
        else
            if (j)
                j=pi[j-1];
            else
                ++i;
    }
    fseek(fout, 0, SEEK_SET);
    fprintf(fout, "%d", ct);
    return 0;
}