Cod sursa(job #1514723)

Utilizator Burbon13Burbon13 Burbon13 Data 31 octombrie 2015 15:15:00
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 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) {
        if(s[j] != p[i])
            if(i)
                i = prefix[i-1];
            else
                ++ j;
        else {
            ++ i;
            ++ j;
            if(i == p_size) {
                ++ af[0];
                if(af[0] <= mmx)
                    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;
}