Cod sursa(job #1650343)

Utilizator Burbon13Burbon13 Burbon13 Data 11 martie 2016 17:50:05
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <cstdio>
#include <cstring>
#define min(a,b) (a < b ? a : b)

using namespace std;

const int nmx = 2000002;

char a[nmx],b[nmx];
int pr[nmx],la,lb,rez[1003];

void prefix(){
    int i = 1, j = 0;
    while(i < la){
        if(a[i] == a[j]){
            pr[i] = j + 1;
            ++ i;
            ++ j;
        }
        else if(j)
            j = pr[j-1];
        else
            ++ i;
    }
}

void kmp(){
    int i = 0, j = 0;
    while(j < lb){
        if(a[i] == b[j]){
            ++ i;
            ++ j;
            if(i == la){
                ++ rez[0];
                if(rez[0] <= 1000)
                    rez[rez[0]] = j - i;
            }
        }
        else if(i)
            i = pr[i-1];
        else
            ++ j;
    }
}

int main(){
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s", a);
    scanf("%s", b);
    la = strlen(a);
    lb = strlen(b);
    prefix();
    kmp();
    printf("%d\n", rez[0]);
    rez[0] = min(rez[0],1000);
    for(int i = 1; i <= rez[0]; ++i)
        printf("%d ", rez[i]);
    return 0;
}