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

#define STRINGLENGTH       2000000
#define PATTERNLENGTH      2000000

typedef char* string;
typedef size_t bool;

/* Static inline necesita trecerea la C99 sau gnu89 */
void precompute(string text, size_t strlens, size_t* out)
{
	size_t j, i;

	j = 0, i = 1;
	while (i < strlens) {
		if (text[j] - text[i])
		{
			if (j > 0)
			{
				j = out[j - 1];
				continue;
			}
			else j--;
		}
		j++;
		out[i] = j;
		i++;
	}
}

int main(int argc, char** argv)
{
    FILE* f = fopen("strmatch.in", "r");
    /* String-ul in care vom efectua cautarea si dimensiunea lui. */
    char* text = calloc(sizeof(char), STRINGLENGTH);
	size_t strlens;
	/* Pattern-ul pe care il vom cauta in string si dimensiunea lui. */
    char* pattern = calloc(sizeof(char), PATTERNLENGTH);
    size_t strlenp;
	/* Vectorul auxiliar specific algoritmului */
    size_t* out = calloc(sizeof(size_t), PATTERNLENGTH);
    int output[1000];
    int y = 0;
	/* Vectorul ce indica daca caracterul de pe pozitia i face parte dintr-un
	   subsir - se foloseste atunci cand se face afisarea textului */
	//char matches[STRINGLENGTH];
	/* In modul verbose, aplicatia tipareste pe cate un rand perechi
	   de numere care semnifica inceputul si respectiv sfarsitul unui
	   match (folositor pentru comparatiile intre algoritmi). */
	//bool verbose, sameColour;
	/* Contori clasici si o variabila care tine numarul de match-uri
	   Aceasta este tiparita ca ultima linie in modul verbose. */
    size_t i, j, t, k, match = 0;

    fgets(pattern, STRINGLENGTH, f);
    strlenp = strlen(pattern);
    if (pattern[strlenp - 1] == '\n') {
        pattern[strlenp - 1] = '\0';
        strlenp--;
    }
    fgets(text, STRINGLENGTH, f);
    strlens = strlen(text);
    if (pattern[strlens - 1] == '\n') {
        pattern[strlens - 1] = '\0';
        strlens--;
    }
    //printf("%s\n%s\n", text, pattern);

	/* Setez vectorul de match-uri pe 0 */
	//memset(matches, 0, sizeof(char) * STRINGLENGTH);
	/* Decid daca sunt sau nu in modul verbose. */
	//verbose = (argc > 1 && !strcmp(argv[1], "--verbose"));
	/* Decid daca voi colora cu aceeasi culoare match-urile (stil grep) */
	//sameColour = (argc > 1 && !strcmp(argv[1], "--samecolour"));
	/* Calculez lungimea textului in care facem cautarea */
	//strlens = read(text);
	
	/* In lista de argumente am fiecare cuvant dupa care caut. Execut
	   algoritmul pentru fiecare din cuvinte. */
	//for (k = 1 + verbose + sameColour; k < argc; k++) {
		/* Pattern-ul curent este urmatorul argument din lista */
		//pattern = argv[k];
		//strlenp = strlen(pattern);
		
		/* Precalculez vectorul */
		precompute(pattern, strlenp, out);
        //printf("%d %d %d\n", out[0], out[1], out[2]);
		
	
		j = 0, match = 0;
		for (i = 0; i < strlens; i++) {
			if (text[i] == pattern[j]) {
				j++;
				if (j == strlenp) {
                    output[y] = i - strlenp + 1;
                    y++;
					match++;
					j = out[j - 1];
				}
			} else {
				if (j != 0) {
					j = out[j - 1];
					i--;
				}
			}
	
        }
        FILE* g = fopen("strmatch.out", "w");
		fprintf(g, "%d\n", match);
        if (match > 1000) match = 1000;
        for (t = 0; t < match; t++) {
            fprintf(g, "%d ", output[t]);
        }
        fprintf(g, "\n");
        fclose(f);
        fclose(g);

	return 0;
}