Cod sursa(job #985218)

Utilizator stefanfStefan Fulger stefanf Data 16 august 2013 22:28:38
Problema Potrivirea sirurilor Scor 18
Compilator c Status done
Runda Arhiva educationala Marime 1.06 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

char s[2000000], p[2000000];
int results[2000000];
int t[2000001];

void prefix(char *str) {
    int n = strlen(str);
    int i, k;

    t[0] = 0;

    k = 0;

    for (i = 1; i < n; i++) {
        while(k > 0 && str[k] != str[i])
            k = t[k];

        if (str[k] == str[i])
            k++;

        t[i] = k;
    }
}

int match(char *text, char *pat) {
    int m, n, i, j;
    int r = 0;

    prefix(pat);

    n = strlen(text);
    m = strlen(pat);

    int k = 0;

    for (i = 0; i < n; i++) {
        while (k > 0 && pat[k] != text[i])
            k = t[k];

        if (pat[k] == text[i])
            k++;

        if (k == m) {
            results[r++] = i - m + 1;
            i -= t[k-1] + 1;
        }
    }

    return r;
}

int main() {

    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    int i, r;

    scanf("%s", p);
    scanf("%s", s);

    r = match(s, p);

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

    return 0;
}