Cod sursa(job #909469)

Utilizator Sm3USmeu Rares Sm3U Data 10 martie 2013 15:44:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <cstdio>
#include <cstring>

#define nMax 2000100

using namespace std;

char a[nMax];
char b[nMax];
int k[nMax];
int n;
int m;
int na;
int afis[1002];

void citire(){
    gets(a + 1);
    gets(b + 1);
    n = strlen(a + 1);
    m = strlen(b + 1);
}

void prefix(){
    int p = 0;
    for(int i = 2; i <= n; ++ i){
        while(p && a[i] != a[p + 1]){
            p = k[p];
        }
        if(a[i] == a[p + 1]){
            p ++;
        }
        k[i] = p;
    }
}

void kmp(){
    int p = 0;
    for(int i = 1; i <= m; ++ i){
        while(p && b[i] != a[p + 1]){
            p = k[p];
        }
        if(b[i] == a[p + 1]){
            p ++;
        }
        if(p == n){
            if(na < 1000){
                afis[na] = i - p;
            }
            na ++;
        }
    }
}

void afisare(){
    printf("%d\n", na);
    if(na > 1000){
        na = 1000;
    }
    for(int i = 0; i < na; ++ i){
        printf("%d ", afis[i]);
    }
}

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

    citire();
    prefix();
    kmp();
    afisare();

    return 0;
}