Алгоритм для нахождения слов-серий в строке - 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;
}

Объяснение кода листинга программы

В этом коде реализован алгоритм поиска слов-серий в строке. Вот список действий, которые происходят в коде:

  1. Функция series принимает два аргумента: исходную строку и подстроку. Если подстрока больше половины исходной строки или подстрока не является серией (одинаковые символы), то возвращается 0. Иначе, находится количество серий в исходной строке, выделяется память под новую строку, и в новой строке копируются символы подстроки. Затем происходит сравнение исходной и новой строки. Если они равны, то возвращается 1, иначе - 0.
  2. Функция substring принимает три аргумента: исходную строку, позицию начала подстроки и длину подстроки. Если не удается выделить память под новую строку, то выводится сообщение об ошибке и возвращается NULL. В противном случае, в новой строке копируются символы из исходной строки, начиная с указанной позиции и длиной указанной длины. Последний символ в новой строке устанавливается в 0.
  3. Функция substrings принимает исходную строку. Сначала определяется длина строки. Затем, пока позиция меньше длины строки, для каждой позиции и длины вычисляется подстрока, и если она является серией, то возвращается 1. После каждой итерации функция series вызывается с аргументами исходной строки и подстроки. Если подстрока является серией, то возвращается 1, иначе вызывается функция substring, чтобы выделить новую подстроку, и процесс повторяется. Если подстрока не является серией, то увеличивается позиция и длина, и процесс повторяется. Если подстрока не найдена, то возвращается 0.
  4. Функция main принимает исходную строку. Сначала вызывается функция substrings с аргументом исходной строки. Затем выводится результат.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

7   голосов , оценка 4.286 из 5
Похожие ответы