Алгоритм для нахождения слов-серий в строке - C (СИ)
Формулировка задачи:
Нужен алгоритм для нахождения слов-серий в строке
Слова-серии – слова, составленные из повторяющихся подслов. Например, 121212 – слово-серия.
Решение задачи: «Алгоритм для нахождения слов-серий в строке»
textual
Листинг программы
#include <stdio.h> #include <stdlib.h> #include <string.h> int series (char *string, char *substring) { int len1=strlen(string); int len2=strlen(substring); if (len2>len1/2 || len1%len2) return 0; int k = len1/len2; char *newstring = (char *)malloc((len1+1)*sizeof(char)); int m=0,i,j; for (i=0; i<k; i++) for (j=0; j<len2; j++) newstring[m++]=substring[j]; //strcat лагает почему-то в новой Studio newstring[m]='\0'; int cmp = strcmp(string,newstring); free (newstring); return (cmp==0 ? 1 : 0); } char *substring(char *string, int position, int length) { char *pointer= (char *)malloc((length+1)*sizeof(string)); int c; if (pointer == NULL) { printf("Unable to allocate memory.\n"); return NULL; } for (c = 0 ; c < length ; c++) { *(pointer+c) = *(string+position-1); string++; } *(pointer+c) = '\0'; return pointer; } int substrings (char *string) { char *pointer; int position = 1, length = 1, temp, string_length; temp = string_length = strlen(string); printf("Substring of "%s" are\n", string); while (position <= string_length) { while (length <= temp) { pointer = substring(string, position, length); printf("%s\n", pointer); if (series(string,pointer)) return 1; free(pointer); length++; } temp--; position++; length = 1; } return 0; } int main() { char *s="111222111222111222111222"; printf ("\nResult is %d",substrings(s)); fflush(stdin); getchar(); return 0; }
Объяснение кода листинга программы
В этом коде реализован алгоритм поиска слов-серий в строке. Вот список действий, которые происходят в коде:
- Функция series принимает два аргумента: исходную строку и подстроку. Если подстрока больше половины исходной строки или подстрока не является серией (одинаковые символы), то возвращается 0. Иначе, находится количество серий в исходной строке, выделяется память под новую строку, и в новой строке копируются символы подстроки. Затем происходит сравнение исходной и новой строки. Если они равны, то возвращается 1, иначе - 0.
- Функция substring принимает три аргумента: исходную строку, позицию начала подстроки и длину подстроки. Если не удается выделить память под новую строку, то выводится сообщение об ошибке и возвращается NULL. В противном случае, в новой строке копируются символы из исходной строки, начиная с указанной позиции и длиной указанной длины. Последний символ в новой строке устанавливается в 0.
- Функция substrings принимает исходную строку. Сначала определяется длина строки. Затем, пока позиция меньше длины строки, для каждой позиции и длины вычисляется подстрока, и если она является серией, то возвращается 1. После каждой итерации функция series вызывается с аргументами исходной строки и подстроки. Если подстрока является серией, то возвращается 1, иначе вызывается функция substring, чтобы выделить новую подстроку, и процесс повторяется. Если подстрока не является серией, то увеличивается позиция и длина, и процесс повторяется. Если подстрока не найдена, то возвращается 0.
- Функция main принимает исходную строку. Сначала вызывается функция substrings с аргументом исходной строки. Затем выводится результат.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д