Cod sursa(job #979585)

Utilizator stefanfStefan Fulger stefanf Data 2 august 2013 00:09:34
Problema Potrivirea sirurilor Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 1.29 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int* table(char *s) {
    int n = strlen(s), pos = 2, cnd = 0;
    int *t = malloc((n + 1) * sizeof(int));

    t[0] = -1;
    t[1] = 0;

    while(pos < n) {
        if (s[pos - 1] == s[cnd]) {
            cnd++;
            t[pos] = cnd;
            pos++;
        } else if (cnd > 0) {
            cnd = t[cnd];
        } else {
            t[pos] = 0;
            pos++;
        }
    }

    return t;
}

int main() {

    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    char *str = malloc(2000000);
    int r = 0;
    int results[2000000];
    char *s, *p;

    scanf("%s", str);
    p = strdup(str);
    scanf("%s", str);
    s = strdup(str);

    free(str);
    
    int *t = table(p);

    int i, m, l = strlen(s);
    i = 0, m = 0;
    while (i + m < l) {
        if (p[i] == s[m + i]) {
            if (i == strlen(p) - 1) {
                results[r++] = m;
                i = 0;
                m++;
            } else {
                i++;
            }
        } else {
            m += i - t[i];
            if (t[i] < 0)
                i = 0;
            else
                i = t[i];
        }
    }

    printf("%d\n", r);
    for (i = 0; i < r; i++)
        printf("%d ", results[i]);

    return 0;
}