Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
0 / 0 / 0
Регистрация: 30.03.2013
Сообщений: 5
1

Реализовать поиск

02.11.2013, 16:03. Показов 2923. Ответов 0
Метки нет (Все метки)

Нужно реализовать 3 поиска: КМП (Кнута-Морриса-Пратта), РК (Рабина-Карпа) и БМ (Бойера-Мура)
Помогите сделать одним цельным кодом с Mainом. Спасибо


Код КМП:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//Префикс-функция для КМП
public static int[] PrefFunc(string x)
        { 
            //Инициализация массива-результата длиной X
            int[] res = new int[x.Length]; 
            int i = 0;
            int j = -1;
            res[0] = -1; 
            //Вычисление префикс-функции
            while (i < x.Length - 1)
            {
                while ((j >= 0) && (x[j] != x[i]))
                    j = res[j];
                i++;
                j++;
                if (x[i] == x[j])
                    res[i] = res[j];
                else
                    res[i] = j;
            }
            return res;//Возвращение префикс-функции
        }
//Функция поиска алгоритмом КМП
public static string KMP(string x, string s)
        {
            string nom = ""; //Объявление строки с номерами позиций
            if (x.Length > s.Length) return nom; //Возвращает 0 поиск если образец больше исходной строки
            //Вызов префикс-функции
            int[] d = PrefFunc(x);
            int i=0, j;
            while (i < s.Length)
            {
                for (i = i, j = 0; (i < s.Length) && (j < x.Length); i++, j++)
                    while ((j >= 0) && (x[j] != s[i]))
                        j = d[j];
                if (j == x.Length)
                    nom = nom + Convert.ToString(i - j) + ", ";
            }
            if (nom != "")
            {
                nom = nom.Substring(0, nom.Length - 2); //Удаление последней запятой и пробела
            }
            return nom; //Возвращение результата поиска
        }
Код РК:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//Хеш-функция для алгоритма Рабина-Карпа
public static int Hash(string x)
        {
            int p = 31; //Простое число
            int rez = 0; //Результат вычисления 
            for (int i = 0; i < x.Length; i++)
            {
                rez += (int)Math.Pow(p,x.Length-1-i)*(int)(x[i]);//Подсчет хеш-функции
            }
            return rez;
        }
//Функция поиска алгоритмом Рабина-Карпа
public static string Rabina(string x, string s)
        {
            string nom = ""; //Номера всех вхождений образца в строку
            if (x.Length > s.Length) return nom; //Если искомая строка больше исходной – возврат пустого поиска
            int xhash = Hash(x); //Вычисление хеш-функции искомой строки
            int shash = Hash(s.Substring(0,x.Length)); //Вычисление хеш-функции первого слова длины образца в строке S
            bool flag;
            int j;
            for (int i = 0; i < s.Length - x.Length; i++)
            {
                if (xhash == shash)//Если значения хеш-функций совпадают
                {
                    flag = true;
                    j = 0;
                    while ((flag == true) && (j < x.Length))
                    {
                        if (x[j] != s[i + j]) flag = false;
                        j++;
                    }
                    if (flag == true) //Если искомая строка совпала с частью исходной
                        nom = nom + Convert.ToString(i) + ", "; //Добавление номера вхождения
                }
                else //Иначе вычисление нового значения хеш-функции
                    shash = (shash - (int)Math.Pow(31,x.Length-1)*(int)(s[i]))*31+(int)(s[i+x.Length]);
            }
            if (nom != "") //Если вхождение найдено
            {
                nom = nom.Substring(0, nom.Length - 2); //Удаление запятой и пробела
            }
            return nom; //Возвращение результата поиска
        }
и 3 код БМ:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
public static char[] SymbolOfX; //Таблица символов искомой строки  
public static int[] ValueShift; //Таблица смещений для символов
public static void ShiftBM(string x) //Процедура - формирование смещений
        {
            int j; //Счетчик
            int k = 0; //Счетчик
            bool fl; //Флаг
            SymbolOfX = new char[x.Length]; //Инициализация
            ValueShift = new int[x.Length]; //Инициализация
            //Цикл по искомой строке без последнего символа
            for (int i = x.Length-2; i >= 0; i--)
            {
                fl = false; //Флаг
                j = 0; //Обнуление
                while ((j<k+1)&&(fl == false))
                {
                    if (SymbolOfX[j] == x[i]) fl = true;
                    j++;
                }
                if (fl == false)
                {
                    SymbolOfX[k] = x[i];
                    ValueShift[k] = x.Length - i - 1;
                    k++;
                }
            }
        }
//Функция поиска алгоритмом БМ
public static string BM(string x, string s)
        {
            bool has, have; //Флаги
            int l,j,i; //Счетчики
            Function.ShiftBM(x); //Вызов процедуры, формирубщей таблицу смещений
            string nom = ""; //Строка с номерами вхождений
            if (x.Length > s.Length) return nom;
            //Основной цикл по исходной строке
            for (i = 0; i < s.Length-x.Length+1; i++)
            {
                j = x.Length - 1;
                have = true;
                //Проверка с последнего символа                
                while ((j >= 0)&&(have == true))
                {
                    //Если не совпадает символ искомой и исходной
                    if (s[i + j] != x[j])
                    {
                        have = false;
                        //Если это последний символ
                        if (j == x.Length-1) 
                        {
                            l = 0;
                            has = false; //Флаг
                            //Поиск символа в таблице смещений
                            while ((l < x.Length)&&(has == false))
                            {
                            //Если символ есть
                                if (s[i + j] == SymbolOfX[l]) 
                                {
                                    has = true; //Изменение флага
                                    i = i + ValueShift[l] - 1; //Сдвиг на величину
                                }
                                l++;
                            }
                            //Если не найден символ в таблице смещений
                            if (has == false) 
                                //Сдвиг на величину искомой строки
                                i = i + x.Length - 1; 
                        }
                    }
                    j--;
                }
                if (have == true)
                    nom = nom + Convert.ToString(i) + ", ";
            }
            //Если строка номеров не пустая
            if (nom != "")
            {
                nom = nom.Substring(0, nom.Length - 2); //Удаление последней запятой и пробела
            }
            return nom; //Возвращение результата поиска
        }
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
02.11.2013, 16:03
Ответы с готовыми решениями:

Реализовать поиск товаров по атрибутам
Здравствуйте. Задание написать программу создания накладной. Набросок есть. На скриншоте рабочий...

Реализовать поиск непересекающихся множеств
можно как то в этом коде реализовать Поиск непересекающихся множеств? using System; using...

Как реализовать линейный и бинарный поиск
Помогите пожалуйста реализовать в C#: 1) Линейный поиск 2) Бинарный поиск 3) Написать строку...

Как реализовать поиск числа проще?
Компьютер загадывает число от 1 до 1000 и сам же должен его угадать. Перебором-то легко, но как...

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.11.2013, 16:03

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Как реализовать таймаут на поиск элемента?
Доброго времени суток всем читающим! Помогите, пожалуйста, реализовать таймаут на C#. ...

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

Как сделать тут реализовать поиск?
using System; using System.Collections.Generic; using System.Linq; using System.Text; using...

Как реализовать поиск простых чисел-близнецов?
Не знаю как реализовать через массив или ещё как-то, чтоб нашло среди простых чисел найденных с...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.