#include <stdio.h>
#include <time.h>

void makeLPS(char* pattern, int* lps, int patternLen) {

	int len = 0;
    int idx = 1;

    while (idx < patternLen) {
        if (pattern[idx] == pattern[len]) {
            ++len;
            lps[idx] = len;
            ++idx;
        }
        else {
            if (len) {
                len = lps[len - 1];
            }
            else {
                lps[idx] = 0;
                ++idx;
            }
        }
    }
}

int getMatches(char* pattern, char* text, int* lps, int* pos, int patternLen, int textLen) {

    int patternIdx = 0;
	int textIdx = 0;

	int noOfPos = 0;

	while ((textLen - textIdx) >= (patternLen - patternIdx)) {

        if (pattern[patternIdx] == text[textIdx]) {
            ++patternIdx;
            ++textIdx;
        }

        if (patternIdx == patternLen) {
            pos = realloc(pos, sizeof(pos) + 4);
            ++noOfPos;
            pos[noOfPos - 1] = textIdx - patternIdx;
            patternIdx = lps[patternIdx - 1];
        }

        else if (textIdx < textLen && pattern[patternIdx] != text[textIdx]) {
            if (patternIdx != 0)
                patternIdx = lps[patternIdx - 1];
            else
                textIdx = textIdx + 1;
        }
    }

    return noOfPos;

}

int main(void)
{
    char* pattern;
    char* text;
    int* lps;
    int* pos;

    FILE *fp = fopen("strmatch.in", "r");

    int patternLen = 0;
    int textLen = 0;

    for(char ch = getc(fp); ch != '\n'; ch = getc(fp)) {
        ++patternLen;
    }

    for(char ch = getc(fp); ch != '\n'; ch = getc(fp)) {
        ++textLen;
    }

    pattern = malloc(sizeof(char)*(patternLen+1));
    lps = calloc(patternLen, sizeof(int));
    text = malloc(sizeof(char)*(textLen+1));
    pos = malloc(sizeof(int)*0);

    fseek(fp, 0, SEEK_SET);

    fscanf(fp, "%s%s", pattern, text);

    fclose(fp);

    clock_t begin = clock();

	makeLPS(pattern, lps, patternLen);

	int noOfPos = getMatches(pattern, text, lps, pos, patternLen, textLen);

	clock_t end = clock();
    double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;

    //printf("%0.15lf\n", time_spent);

    fp = fopen("strmatch.out", "w");

    fprintf(fp, "%d\n", noOfPos);

    for(int i = 0; i < noOfPos; i++) {
        fprintf(fp, "%d ", pos[i]);
    }

    fclose(fp);

	return 0;
}