Cod sursa(job #1439780)

Utilizator GeiGeiGeorge Cioroiu GeiGei Data 23 mai 2015 09:48:50
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
//005
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

int main() {
    FILE* fi = fopen("strmatch.in", "rt");
    FILE* fo = fopen("strmatch.out", "wt");

    //long tot = 2000005;
    char n[2000005], m[2000005];
    long pi[200005], poz[1010], cur = 0;*/


    fgets(n, 2000005, fi);
    fgets(m, 2000005, fi);

    long sn = (long)strlen(n), sm = (long)strlen(m), q = -1, k = -1;
    pi[0] = -1;
    for (long i = 1; i < sn; i++) {
        while (k >= 0 && n[k + 1] != n[i])
            k = pi[k];
        if (n[k + 1] == n[i])
            k++;
        pi[i] = k;
    }

    for (long i = 0; i < sm; i++) {
        while (q >= 0 && n[q + 1] != m[i])
            q = pi[q];
        if (n[q + 1] == m[i])
            q++;
        if (q == sn - 1) {
            if (cur <= 1000)
                poz[cur] = i - sn + 1;
            cur++;
        }
    }

    long l = min((long)1000, cur);
    fprintf(fo, "%ld", cur);
    for (int i = 0; i < l; i++)
        fprintf(fo, "%ld ", poz[i]);
    return 0;
}