Cod sursa(job #2595953)

Utilizator k2e0e0w3qDumitrescu Gheorghe k2e0e0w3q Data 8 aprilie 2020 19:40:02
Problema Potrivirea sirurilor Scor 40
Compilator cpp-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 (isalnum(t[i])){
        if (t[i]==t[len])
            pi[i++]=++len;
        else
            if (len)
                len=pi[len-1];
            else
                pi[i++]=0;
    }
}
int main (void) {
    FILE *fin=fopen ("strmatch.in", "r"),
         *fout=fopen ("strmatch.out", "w");
    fgets(t, sizeof t, fin);
    fgets(s, sizeof s, fin);

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