Составить блок схему для алгоритма Апостолико-Крочемора
Выполняю лабораторную работу по этому алгоритму, в интернете информации почти не нашёл, в списках литературы ее крайне мало. Прошу помочь, без всяких подколов и прочего
Понимаю вашу ситуацию. Алгоритм Апостолико-Крочемора действительно не самый распространенный, и найти информацию о нем может быть сложно. Давайте попробуем составить блок-схему для этого алгоритма. Вот основные шаги:
1. Начало
2. Ввод данных:
- Ввод текста T
- Ввод образца P
3. Предварительная обработка:
- Вычисление массива смещений для образца P
- Вычисление массива совпадений для образца P
4. Инициализация переменных:
- i = 0 (позиция в тексте T)
- j = 0 (позиция в образце P)
5. Основной цикл поиска:
Пока i + длина(P) <= длина(T):
5.1. Сравнение символов:
Если T[i+j] = P[j]:
- j = j + 1
- Если j = длина(P):
- Найдено совпадение, вывести позицию i
- i = i + 1
- j = 0
Иначе:
- Если j = 0:
i = i + 1
- Иначе:
i = i + max(j - массив_совпадений[j-1], 1)
j = массив_смещений[j-1]
6. Конец
Блок-схема будет выглядеть примерно так:
```
[Начало]
|
v
[Ввод T и P]
|
v
[Вычисление массивов смещений и совпадений]
|
v
[Инициализация i=0, j=0]
|
v
[Основной цикл поиска]
| /\
да |
┌--------┐
| | нет
v |
[Сравнение T[i+j] и P[j]]
| /\
да |
| нет
v |
[Обработка совпадения] [Обработка несовпадения]
| |
| ┌-----------------┘
| |
v v
[Обновление i и j]
|
|
└─> [Проверка условия цикла]
|
v
[Конец]
```
Это базовая блок-схема алгоритма Апостолико-Крочемора. Возможно, вам потребуется добавить дополнительные детали или уточнения в зависимости от конкретных требований вашей лабораторной работы.
Помните, что важно понимать каждый шаг алгоритма. Если у вас возникнут вопросы по конкретным частям алгоритма, не стесняйтесь спрашивать для дальнейшего уточнения.
а путём обычного перебора не пойдёт
#include <windows.h>
#include <string>
#include <iostream>
#include <string.h>
#include <iomanip>
#include <vector>
using namespace std;
int main(int argc, char **argv)
{
system("chcp 1251 > nul"); // Руссификация сообщений
setlocale(LC_ALL, "Russian");
string s= "012345056056789";
string ss= "567";
string s0= "Подстрока не найдена";
size_t i=0; size_t i1=0; size_t is= s.length(); size_t iss= ss.length();
size_t flag= 0;
do
{
if(ss[i1]==s[i]) { cout << s[i1] << " = " << s[i] << endl; i++; i1++; flag++; }
else { cout << ss[i1] << " != " << s[i] << endl; i1=0; i++; flag=0; }
}while ( (i<(is-iss+1)) || (flag!=iss) );
cout << "Флаг=" << flag << "\ti= " << i << endl;
if(flag!=0) { s0=s.substr(i-iss,iss); }
cout << s0 << endl;
cout << endl << "Хелло Ворлд" << endl;
system("pause"); // system("pause > nul");
return 0;
}
Алгоритм Апостолико-Крочемора (Apostolico-Crochemore) — это алгоритм поиска подстроки в строке, основанный на предобработке шаблона для эффективного поиска. Вот как можно представить блок-схему для его реализации.
Основные этапы алгоритма:
Предобработка шаблона:
Создание массива префиксов (Z-функции).
Построение массива сдвигов.
Поиск подстроки:
Сравнение символов строки с шаблоном.
Использование предвычисленных сдвигов для оптимизации.
Упрощённое описание блок-схемы:
Начало.
Ввод строки T (текста) и шаблона P.
Предобработка шаблона:
Построить Z-функцию для шаблона P.
Вычислить массив сдвигов.
Инициализация позиции i = 0 для текста.
Пока i <= N - M (где N — длина текста, M — длина шаблона):
Сравнить символы T и P начиная с i.
Если совпадение найдено, вывести позицию.
Переместить i на значение из массива сдвигов.
Конец.
Для создания диаграммы можно использовать следующую структуру:
Начало.
Блок "Ввод текста и шаблона".
Блок "Построение Z-функции".
Блок "Создание массива сдвигов".
Блок цикла i <= N - M:
Внутри: "Сравнение символов".
Проверка совпадения.
Обновление позиции i.
Конец.