Cod sursa(job #1439788)

Utilizator GeiGeiGeorge Cioroiu GeiGei Data 23 mai 2015 09:58:21
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
//005
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <list>
#include <algorithm>
#define li list<long>::iterator

using namespace std;

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

    char* n = (char*)malloc(2000001 * sizeof(char));
    char* m = (char*)malloc(2000001 * sizeof(char));

    fscanf(fi, "%s%s", n, m);
   // printf("%s\n%s", n, m);

    long sn = strlen(n), sm = strlen(m), q = -1, k = -1, l = 0;
    long* pi = (long*)malloc(sn * sizeof(long));
    list<long> ord;

    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) {
            l++;
            if (l <= 1000)
                ord.push_back(i - sn + 1);
        }
    }

    fprintf(fo, "%ld\n", l);
    for (li it = ord.begin(); it != ord.end(); it++)
        fprintf(fo, "%ld ", *it);

    return 0;
}