Как найти шаблон в массиве целых чисел?
Неделю назад я получил домашнее задание, где мне нужно написать функцию на языке C. Функция получает единственный массив положительных целых чисел и должна возвращать следующее число в массиве. Массивы выглядят примерно так: {1,2,3,1,2,3,4,1,2,3,1,2,3,4,1,2,3,-1}; -1 означает конец массива.
Я знаю, что число, которое должна возвращать функция, равно 1, однако как я могу закодировать алгоритм поиска шаблонов? Я не нашел никакого решения в Интернете, поскольку все остальные вопросы о поиске шаблонов связаны со строками, где шаблон, который необходимо найти, уже указан.
2 ответа
Если узор имеет длину 1у тебя будет a[k+1] == a[k] для всех возможных k.
в более общем плане у вас будет a[k+plen] == a[k] для правильного plen (длина выкройки) и все возможные k.
так определите plen начиная с 1... в вашем случае вы получите 7 потому как a[7]==a[0], a[8]==a[1],... a[16]==a[9]так что просто вернись a[17-7].
Основываясь на ответе pmg, один простой способ определитьplen использовать грубую силу:
Начнем с предположения plen равно 1, и увеличить plen по 1 пока не будет найден узор.
Вы находите шаблон, проверяя, начинается ли последовательность plen элемент соответствует первому plenэлементы массива. Так что если нынешнийplen является 3, затем вы проверяете, находятся ли элементы в индексе 3 к 5 (включительно) соответствует элементам по индексу 0 к 2(включительно). Если они совпадают, вы проверяете следующую последовательность, начиная с индекса6. И так далее.
Если маркер конца массива -1 находится в той последовательности, которую вы только что ищете, тогда у вас есть plen. И если последовательность не совпадает, начните с увеличенногоplen и попробуй еще раз.