Cod sursa(job #2429189)

Utilizator CristianaLazarCristiana Lazar CristianaLazar Data 8 iunie 2019 12:46:52
Problema Potrivirea sirurilor Scor 36
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

	
#define MAX 2000005
int next[MAX];

void initnext(char *p){
    int i, j, M = strlen(p) -1;
    next[0] = -1;
    for(i = 0, j = -1; i < M; i++, j++, next[i] = j){
        while((j>=0) && (p[i] != p[j])){
            j = next[j];
        }
    }
}

int cautKMP(char *p, char *a){
    int i, j;
    int N = strlen(a) -1;
    int M = strlen(p) -1;

    initnext(p);
    for(i = 0, j = 0; i < N && j < M; i++,j++){
        while((j>=0) && a[i] != p[j]){
            j = next[j];
        }
    }   
    if(j == M) {
        return i-M;
    }
    else return i;
}

int main(){
    char *P, *A, *a;
    P = calloc(MAX, sizeof(char));
    A = calloc(MAX, sizeof(char));

    int nr = 0, i, k;
    int *v = calloc(MAX, sizeof(int));
    freopen("strmatch.in", "r", stdin);	
	freopen("strmatch.out", "w", stdout);

    fgets(P, MAX, stdin);	
	fgets(A, MAX, stdin);

    int M = strlen(A) -1;
    // int N = strlen(P) -1;
    a = A;
    for(i = 0; i < M; i++){
        k = cautKMP(P,a);

        if(k != M) {
            if(nr) v[nr] = v[nr-1] + k + 1;
            else v[nr] = k;
            nr++;
        }
        a = a+k+1;
        M -= k + 1;
    }
    printf("%d\n", nr);

    for(k = 0; k < nr; k++){
          printf("%d ", v[k]);
    }

    
    free(P);
    free(A);
    free(v);

    return 0;
}