Cod sursa(job #1073918)

Utilizator alin_c9UAIC Alin Ciocan alin_c9 Data 6 ianuarie 2014 21:59:12
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include<stdio.h>
#include<string.h>

#define NMAX 2000000

char text[NMAX], pat[NMAX];

int func[NMAX];


void failureFunction() {
    int lung = strlen(pat);
    int i = 0, j = 0;
    func[0] = 0;

    for(int i = 1; i < lung; ++i) {
        if(pat[i] == pat[j]) {
            j++;
        } else {
            j = (pat[i] == pat[0]) ? 1 : 0;
        }
        func[i] = j;
    }


}
int gasit[NMAX], gasitLen = 0;

void kmp() {
    int patLen = strlen(pat), textLen = strlen(text);
    for(int i = 0, j = 0; i < textLen; i++) {
        if(text[i] == pat[j]) {
            j++;
        } else {
            j = j > 1? func[j - 1] : 0;
            if(text[i] == pat[j]) {
                j++;
            }

        }
        if(j == patLen)  {
          //  printf("Gasit: %d\n", i - j + 1);
            gasit[gasitLen++] = i - j + 1;
            i -= func[j-1];
            j = func[j-1];
        }
    }
}

int main() {
    freopen("strmatch.in","r",stdin);
   freopen("strmatch.out","w",stdin);

    scanf("%s",pat);
    scanf("%s",text);

    failureFunction();
    kmp();

    // afisare
    printf("%d\n", gasitLen);
     for ( int i = 0; i < gasitLen ; i++ ) {
           printf("%d ", gasit[i]);
     }




    /*   int lung = strlen(pat);
       for ( int i = 0; i < lung ; i++ )
           printf("%d ", func[i]);
    */
    // printf("%s -> %s",pat,text);

    return 0;
}