Составить блок схему для алгоритма Апостолико-Крочемора

Question

Составить блок схему для алгоритма Апостолико-Крочемора

NickS Ученик (103), закрыт 4 недели назад

Выполняю лабораторную работу по этому алгоритму, в интернете информации почти не нашёл, в списках литературы ее крайне мало. Прошу помочь, без всяких подколов и прочего

Answer 1

Понимаю вашу ситуацию. Алгоритм Апостолико-Крочемора действительно не самый распространенный, и найти информацию о нем может быть сложно. Давайте попробуем составить блок-схему для этого алгоритма. Вот основные шаги:

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
[Конец]
```

Это базовая блок-схема алгоритма Апостолико-Крочемора. Возможно, вам потребуется добавить дополнительные детали или уточнения в зависимости от конкретных требований вашей лабораторной работы.

Помните, что важно понимать каждый шаг алгоритма. Если у вас возникнут вопросы по конкретным частям алгоритма, не стесняйтесь спрашивать для дальнейшего уточнения.

Answer 2

Алгоритм Апостолико-Крочемора (Apostolico-Crochemore) — это алгоритм поиска подстроки в строке, основанный на предобработке шаблона для эффективного поиска. Вот как можно представить блок-схему для его реализации.
Основные этапы алгоритма:

Предобработка шаблона:
Создание массива префиксов (Z-функции).
Построение массива сдвигов.

Поиск подстроки:
Сравнение символов строки с шаблоном.
Использование предвычисленных сдвигов для оптимизации.

Упрощённое описание блок-схемы:

Начало.
Ввод строки T (текста) и шаблона P.
Предобработка шаблона:
Построить Z-функцию для шаблона P.
Вычислить массив сдвигов.
Инициализация позиции i = 0 для текста.
Пока i <= N - M (где N — длина текста, M — длина шаблона):
Сравнить символы T и P начиная с i.
Если совпадение найдено, вывести позицию.
Переместить i на значение из массива сдвигов.
Конец.

Для создания диаграммы можно использовать следующую структуру:

Начало.
Блок "Ввод текста и шаблона".
Блок "Построение Z-функции".
Блок "Создание массива сдвигов".
Блок цикла i <= N - M:
Внутри: "Сравнение символов".
Проверка совпадения.
Обновление позиции i.
Конец.

Answer 3

Батаев Дмитрий Просветленный (23228) 1 месяц назад

а путём обычного перебора не пойдёт

 #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; 
}

Батаев ДмитрийПросветленный (23228) 1 месяц назад

кое-что убрать лишнее и совсем будет хорошо, а товарищи академики усложнили донельзя простой алгоритм

Батаев ДмитрийПросветленный (23228) 1 месяц назад

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]) { i1++; flag++; }
else { i1=0; flag=0; }
i++;
}while ( (i<(is-iss+1)) || (flag!=iss) );
if(flag!=0) { s0=s.substr(i-iss,iss); }
cout << s0 << endl;

Батаев Дмитрий, а если s = "01012" ss= "012"

Батаев ДмитрийПросветленный (23228) 1 месяц назад

 string s= "01012";  //"5624245"; 
    string ss="012";    // "245"; 
    string s0= "Подстрока не найдена"; 
    size_t i=0; size_t i1=0; 
        size_t is= s.length(); size_t iss= ss.length(); 
            size_t flag= 0; int n; 
    do 
    { 
        if(ss[i1]!=s[i]) { cout << ss[i1] << " != " << s[i] << endl; n= 0; } 
        if(ss[i1]==s[i]){ cout << ss[i1] << " = " << s[i] << endl; n= 1; } 
 
        switch(n) 
        { 
            case 0: i1=0; if (!flag) {i++;} flag=0; break; 
            case 1: i1++; flag++; i++; break; 
        } 
 
    }while ( (i<is) || (flag!=iss) ); 
 
    cout << "Флаг=" << flag << "\ti= " << i << endl; 
 
    if(flag!=0) { s0=s.substr(i-iss,iss); } 
        cout << s0 << endl;
Попробуй так. Что мы глупее академиков?

Батаев ДмитрийПросветленный (23228) 4 недели назад

 //string s= "01012"; 
    string s= "56242452400"; 
    //string ss="012"; 
    string ss= "245"; 
    string s0= "Подстрока не найдена"; 
    size_t i=0; size_t i1=0; 
        size_t is= s.length(); size_t iss= ss.length(); 
    size_t flag= 0; 
    for (i=0; i<(is-iss+1); i++) 
    { 
        i1=0; 
        do 
        { 
            if (s[i]==ss[i1]) { cout << s[i] << " = " << ss[i1] << endl; i1++; i++; flag++; } 
            if (s[i]!=ss[i1]) { cout << s[i] << " != " << ss[i1] << endl; 
                                if (flag==iss) break; 
                                if (flag!=0) { i--; } flag= 0; break; } 
 
        }while(i1<iss); 
        if (flag==iss) break; 
    } 
    if(flag==iss) { s0=s.substr(i-iss,iss); } 
        cout << s0 << endl; 
        cout << "i= " << i << endl;

Батаев Дмитрий, усложняем задачу: s = "0101012" ss= "01012"

Батаев ДмитрийПросветленный (23228) 4 недели назад

 string s= "01012"; 
    string ss="012"; 
 
    //string s= "56242452400"; 
    //string ss= "245"; 
 
    //string s= "0101012"; 
    //string ss= "01012"; 
 
    string s0= "Подстрока не найдена"; 
    size_t i=0; size_t i1=0; 
        size_t is= s.length(); size_t iss= ss.length(); 
        cout << "iss= " << iss << "\tis= " << is << endl; 
 
    size_t flag= 0; size_t i0; 
 
    for (i=0; i<is-1; i++) 
    { 
        i1=0; i0= i; 
        while(i1<iss) 
        { 
            if ( s[i0]==ss[i1] ) 
                { cout << s[i0] << " = " << ss[i1] << "\ti0= " << i0 << "\ti1= " << i1 << endl; 
                    i1++; i0++; flag++; if

Батаев ДмитрийПросветленный (23228) 4 недели назад

(flag==iss) break; }

if ( s[i0]!=ss[i1] )
{ cout << s[i0] << " != " << ss[i1] << "\ti0= " << i0 << "\ti1= " << i1 << endl;
/*if (flag!=0) { i--; }*/
flag= 0; break; }

}

if (flag==iss) break;
}

cout << "i= " << i << endl;
if(flag==iss) { s0=s.substr(i,iss); }
cout << s0 << endl;

Батаев ДмитрийПросветленный (23228) 4 недели назад

ещё варианты давай пока не найдём правильный вариант. Здесь просто окно просматривается и потом только ненужные позиции в конце окна исходной строки правильно отбросить

Вот и получился тот самый прямой поиск. Если убрать ненужные переменные, то его можно записать так:

 for (i = 0; i < is - iss + 1; ++i)  
{  
    for(i1 = 0; i1 < iss && s[i+i1] == ss[i1]; ++i1) ; 
    if(i1 == iss)  
    { 
        s0 = s.substr(i, iss); 
        break; 
    } 
}

Работает и в определённых ситуациях даже вполне годится. Но проблема в том, что никак не используется информация об уже произведённых сравнениях. Если эту информацию использовать, можно продвигаться по просматриваемой строке быстрее (вместо i+1 получить i+k). Вот и напридумывали всяких алгоритмов , как двигаться по строке быстрее.

Батаев ДмитрийПросветленный (23228) 4 недели назад

потом от string перейдём к char с \0 ограничителем, а не использовать длину стринга, проверяя только на \0 обе строки

Батаев ДмитрийПросветленный (23228) 3 недели назад

а можно попробовать )) тем более я смотрю реализация по Н в худшем случае сложны в реализации

ПапаВысший разум (148310) 3 недели назад

Что-то вспомнился доктор из "Дракула мёртвый и довольный", который всех лечил клизмой. Его дочь укусил вампир, и Ван Хельсинг принялся объяснять сложный способ лечения. А доктор, выслушав всё это:
-- А клизма ей не поможет?

Батаев Дмитрий Просветленный (23228) Папа, просто, как всё гениальное... Чем проще, тем лучше... А ларчик просто открывался... Ну, и будь проще и к тебе потянутся люди против ОДНОГО, простота - хуже воровства