Cod sursa(job #985254)

Utilizator stefanfStefan Fulger stefanf Data 17 august 2013 02:25:14
Problema Potrivirea sirurilor Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 1.33 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

char text[2000000], pat[2000000];
int results[1002];
int t[2000001];

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

    t[1] = 0;

    k = 0;

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

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

        t[i] = k;
    }
}

int length(char *t) {
    int i;

    for (i = 1; (t[i] >= 'A' && t[i] <='Z') || (t[i] >= 'a' && t[i] <= 'z') || (t[i] >= '0' && t[i] <= '9'); i++);

    return i - 1;
}

int match() {
    int m, n, i;
    int r = 0;

    prefix(pat);

    n = length(text) + 1;
    m = length(pat);

    int k = 0;

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

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

        if (k == m) {
            k = t[m];
            if (r < 1000)
                results[r++] = i - m;
            else 
                return r;
        }
    }

    return r;
}

int main() {

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

    int i, r;

    scanf("%s", pat+1);
    pat[0] = ' ';
    scanf("%s", text+1);
    text[0] = ' ';

    r = match();

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

    return 0;
}