// SPDX-License-Identifier: GPL-2.0-or-later
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define LEN_MAX 128

bool find_string(char *sub, char *str, int len_of_str, int len_of_sub)
{
	int arr_value[256];

	for (int i = 0; i < 256; i++)
		arr_value[i] = len_of_sub;

	for (int j = 0; j < len_of_sub - 1; j++) {
		char c = sub[j];

		arr_value[c] = len_of_sub - j - 1;
	}

	arr_value[sub[len_of_sub-1]] = len_of_sub;

	for (int i = 0; i < len_of_sub; i++) {
		char c = sub[i];

		printf("%d\n", arr_value[c]);
	}

	bool found = false;

	if (len_of_sub > len_of_str)
		return false;

	for (int ind_of_str = 0; ind_of_str < len_of_str - len_of_sub + 1;) {
		int j;

		for (j = len_of_sub - 1; j >= 0; j--) {
			if (sub[j] != str[ind_of_str + j])
				break;
		}

		if (j < 0) {
			found = true;
			break;
		}

	ind_of_str += arr_value[str[ind_of_str+j]];

	}
	return found;
}

int characters_input(char **str)
{
	int curr_size = LEN_MAX;
	int lenght;

	if (*str != NULL) {
		int i = 0;
		char c = EOF;

		while ((c = getchar()) != '\n' && c != EOF) {
			*str[i++] = c;
			if (curr_size == i) {
				curr_size = i + LEN_MAX;
				*str = realloc(*str, curr_size);
			}
			lenght = i;
		}
		*str[i] = '\0';
		*str = realloc(*str, lenght + 1);
	}

	return lenght;
}

int main(void)
{
	int len_of_str;
	int len_of_sub;
	char *str = malloc(LEN_MAX * sizeof(char));
	char *sub_str = malloc(LEN_MAX * sizeof(char));

	printf("Enter your string:\n");
	len_of_str = characters_input(&str);

	printf("Enter your substring:\n");
	len_of_sub = characters_input(&sub_str);

	if (find_string(sub_str, str, len_of_str, len_of_sub))
		printf("Substring is found!");
	else
		printf("Substring isn't found!");

	free(str);
	free(sub_str);
	return 0;
}