Cod sursa(job #632881)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 12 noiembrie 2011 14:55:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<cstdio>
#include<string.h>
#define N 2000005


char A[N];
char B[N];
int pi[N];
int NA, NB;
int contor;
int arr[1005];
void Prefix(char* a) {

    int j = 0;
    pi[0] = 0;
    for(int i = 1; i < NA; i++) {
        while((a[j] != a[i]) && (j != 0)) {
            j = pi[j-1];
        }
        if (a[j] == a[i])
         pi[i] = ++j;
    }
    return;
}
void kmp() {
    int j = 0;
    for(int i = 0; i < NB; i++) {
        while((B[i] != A[j]) && (j != 0)) {
            j = pi[j-1];
        }
        if (B[i] == A[j])
         if(j == NA - 1) {
             contor++;
             j = pi[j];
             if (contor <= 1000) {
                 arr[contor] = i - NA + 1;
             }
         }
         else
          j++;
    }
}
int min(int a, int b) {
    if (a < b) return a;
    return b;
}
int main() {
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    scanf("%s %s",&A, &B);
    NA = strlen(A);
    NB = strlen(B);
    Prefix(A);
    kmp();
    printf("%d\n",contor);
    for(int i = 1; i <= min(contor, 1000); i++)
     printf("%d ",arr[i]);
    return 0;
}