#include <ctype.h>
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
 
 
const int PARAMS_NUM    = 4; 
const int MAX_INPUT_LEN = 20000; 
 
FILE *open_file(const char *filename, const char *access); 
void read_data (char data[], FILE* input_file); 
void find_patterns(char data[], int pattern_len, FILE* output_file); 
 
int main(int argc, char *argv[]) 
{ 
	if(argc != PARAMS_NUM) 
	{ 
		fprintf(stderr, "Invalid number of parameters, usage : pattern <encrypted> <pattern len> <output>\n"); 
		fprintf(stderr, "For example : pattern encrypt.txt 3 output.txt\n"); 
		exit(-1); 
	} 
 
	FILE* input_file  = open_file(argv[1], "r"); 
	FILE* output_file = open_file(argv[3], "w"); 
 
	int   pattern_len = atoi(argv[2]); 
	if( pattern_len <= 0) 
	{ 
		fprintf(stderr, "Invalid pattern len\n"); 
		exit(-1); 
	} 
 
	char  input_data[MAX_INPUT_LEN]; 
	read_data(input_data, input_file); 
 
	find_patterns(input_data, pattern_len, output_file); 
 
	fclose(input_file); 
	fclose(output_file); 
 
	return 0; 
} 
 
FILE *open_file(const char *filename, const char *access) 
{ 
	FILE *file_handle; 
 
	file_handle = fopen(filename, access); 
	if(file_handle == NULL) 
	{ 
		fprintf(stderr,"Unable to open file %s\n", filename); 
		exit(-1); 
	} 
 
	return file_handle; 
} 
 
void read_data(char data[], FILE* input_file) 
{ 
	int i = 0; 
	int read_char; 
 
	while( (read_char = fgetc(input_file)) != EOF ) 
	{ 
		read_char = toupper(read_char); 
		if( ('A' <= read_char) && (read_char <= 'Z') ) 
		{ 
			data[i++] = read_char; 
		} 
	} 
 
	data[i] = 0; 
} 
 
void find_patterns(char data[], int pattern_len, FILE* output_file) 
{ 
	char* pattern = (char *)malloc(sizeof(char) * (pattern_len + 1)); 
	if(pattern == 0) 
	{ 
		fprintf(stderr, "Unable to allocate memory\n"); 
		exit(-1); 
	} 
 
	char* data_start = data; 
 
	while(strlen(data_start) >= pattern_len*2) // Possible to find a pattern twice 
	{ 
		strncpy(pattern, data_start, pattern_len); 
		pattern[pattern_len] = 0; 
 
		int first_pattern_pos = data_start - data; 
 
		char* cur_pos = data_start + pattern_len; 
		data_start++; 
 
		int first_print = 1; 
 
		while(strlen(cur_pos) >= pattern_len) 
		{ 
			char* pattern_pos = pattern; 
			char* data_pos    = cur_pos; 
 
			int flag = 1; 
 
			while((*pattern_pos) && flag) 
			{ 
				if( (*pattern_pos++) != (*data_pos++) ) 
				{ 
				   flag = 0; 
				} 
			} 
 
			if(flag) 
			{ 
				if(first_print) 
				{ 
					fprintf(output_file, "\nFirst appearance of %s is at position %d\n", 
										 pattern, first_pattern_pos); 
					first_print = 0; 
				} 
 
				fprintf(output_file, "Next appearance is at position %d\n", (cur_pos - data)); 
			} 
 
			cur_pos++; 
		} 
	} 
 
	free(pattern); 
}