#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_LENGTH 2000005
#define MAX_POS 1000

int *compute_prefix(char *str)
{
    int j = 0, i = 1;
    int n = strlen(str) - 1;

    int *p = calloc(n, sizeof(int));
    if (!p) return NULL;

    while (i < n) {
        if (str[i] == str[j]) {
            p[i] = j+1;
            i++; j++;
        } else {
            if (j == 0) {
                p[i] = 0;
                i++;
            } else {
                j = p[j-1];
            }
        }
    }

    return p;
}

int *kmp(char *text, char *pattern, int *p, int *count) {
    int m = strlen(text) - 1;
    int n = strlen(pattern) - 1;

    int i = 0, j = 0;

    int *pos = calloc(MAX_POS, sizeof(int));
    if (!pos) return NULL;

    while(i < m) {
        if (text[i] == pattern[j]) {
            if (j == n-1) {
                (*count)++;

                if (*count <= MAX_POS)
                    pos[(*count)-1] = i - n + 1;

                j = p[j-1];
            } else {
                i++; j++;
            }
        } else {
            while (j > 0 && text[i] != pattern[j])
                j = p[j-1];
            
            if (text[i] == pattern[j])
                j++;
            i++;
        }
    }

    return pos;
}

int main()
{
    FILE *fin = fopen("strmatch.in", "r");
    if (!fin) return -1;

    FILE *fout = fopen("strmatch.out", "w");
    if (!fout) return -1;

    char *text = calloc(MAX_LENGTH, sizeof(char));
    char *pattern = calloc(MAX_LENGTH, sizeof(char));

    fgets(pattern, MAX_LENGTH, fin);
    fgets(text, MAX_LENGTH, fin);

    int *p = compute_prefix(pattern);
    int n = strlen(pattern) - 1;

    int count = 0;
    int *pos = kmp(text, pattern, p, &count);
    if (!pos) return -1;

    fprintf(fout, "%d\n", count);
    int size = (count < MAX_POS) ? count : MAX_POS;
    for (int i = 0; i < count; i++)
        fprintf(fout, "%d ", pos[i]);

    fclose(fin);
    fclose(fout);

    return 0;
}