Cod sursa(job #2630661)

Utilizator doyouhavethetimeStanculescu Gabriel doyouhavethetime Data 26 iunie 2020 16:52:16
Problema Potrivirea sirurilor Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.99 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 (isspace(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;
}