Cod sursa(job #985249)

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

char s[2000000], p[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 match(char *text, char *pat) {
    int m, n, i;
    int r = 0;

    prefix(pat);

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

    int k = 0;

    for (i = 1; i <= n; i++) {
        while (k > 0 && 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", p+1);
    p[0] = ' ';
    scanf("%s", s+1);
    s[0] = ' ';

    r = match(s, p);

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

    return 0;
}