Cod sursa(job #1514721)

Utilizator Burbon13Burbon13 Burbon13 Data 31 octombrie 2015 15:12:21
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <cstdio>
#include <cstring>
using namespace std;

const int nmx = 2000005;
const int mmx = 1000;

char s[nmx],p[nmx];
int prefix[nmx],af[mmx+2],s_size, p_size;

void make_prefix(){
    int i = 0, j = 1;
    while(j < p_size){
        if(p[i] != p[j])
            if(i)
                i = prefix[i-1];
            else
                ++ j;
        else{
            prefix[j] = ++i;
            ++ j;
        }
    }
}

void kmp(){
    int i = 0, j = 0;
    while(j < s_size && af[0] < mmx){
        if(s[j] != p[i])
            if(i)
                i = prefix[i-1];
            else
                ++ j;
        else{
            ++ i;
            ++ j;
            if(i == p_size)
                af[++af[0]] = j-p_size;
        }
    }
}

void output(){
    printf("%d\n", af[0]);
    for(int i = 1; i <= af[0]; ++i)
        printf("%d ", af[i]);
}

int main(){
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s %s",p, s);
    p_size = strlen(p);
    s_size = strlen(s);
    make_prefix();
    kmp();
    output();
    return 0;
}