Поиск подпоследовательности в последовательности
Определите, сколько раз во входной последовательности встречается подпоследовательность 1, 2, 3, . . . , 10.
Помогите пожалуйста, ни одной мысли по решению.
Имеющийся код:
/*Определите, сколько раз во входной последовательности встре-
чается подпоследовательность 1, 2, 3, . . . , 10..*/
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stddef.h>
#include <string.h>
#include <malloc.h>
#include <math.h>
#include <ctype.h>
#include <limits.h>
#include <float.h>
#define NUM_MEMB 32
int main()
{
int *arrX = (int*)malloc(sizeof(int) * NUM_MEMB);
printf("arrX:\n");
for(int i = 0; i < NUM_MEMB; i++)
{
//arrX[i] = (rand()- RAND_MAX/2)%10 + i;
arrX[i] = rand()%10;
//printf(" %i ",arrX[i]);
}
arrX[5] = 1;
arrX[6] = 2;
arrX[7] = 3;
arrX[8] = 4;
arrX[9] = 5;
arrX[10] = 6;
arrX[11] = 7;
arrX[12] = 8;
arrX[13] = 9;
arrX[14] = 10;
for(int i = 0; i < NUM_MEMB; i++)
printf(" %i ",arrX[i]);
printf("\n");
printf("Hello World!\n");
return 0;
}
Ответы (1 шт):
Пусть a последовательность длины n, b - последовательность длины m. Будем искать сколько раз последовательность b может быть подпоследовательностью последовательность a. Для удобства индексируем последовательности с единицы.
Введём функцию c(i, j) которая берёт из a первые i элементов, из b - первые j элементов и решает задачу для этих частичных последовательностей.
Число которое нас интересует - c(n, m).
Как можно вычислить c(i, j)?
Если a[i] = b[j], то подпоследовательность или заканчивается в a[i] или заканчивается раньше. Первых c(i - 1, j - 1) штук, вторых - c(i - 1, j) штук.
Если a[i] != b[j], то любая подпоследовательность заканчивается раньше. Таких c(i - 1, j) штук.
Заметим что c(i, 0) = 1 - в любой последовательности одна пустая подпоследовательность. И c(0, j > 0) = 0.
Имея набор c(i, *) можно вычислить c(i + 1, *).