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

Написать программу для поиска подстроки в строке с визуализацией основных этапов сравнения

03.12.2013, 23:48. Просмотров 656. Ответов 0
Метки нет (Все метки)

Прошу помочь натолкнуть на мысль как реализовать визуализацию основных этапов сравнения строк т.к. не могу понять как рациональней это сделать. Задание звучит так:
"Разработать программу реализации сравнения строк по алгоритмам Кнута-Морриса-Пратта и Бойера-Мура с визуализацией основных этапов сравнения"

Исходников алгоритмов на просторах интернета вагон и объяснений к ним тоже. К алгоритмам вопросов нет, но вот как интегрировать визуализацию в алгоритмы, это конечно вопрос. Я думал возможно написать метод, который будет вызываться на определенных этапах сравнения и будет отображать происходящее внутри алгоритма, но я думаю может у кого-то найдется лучше идея?

Кликните здесь для просмотра всего текста
C#
1
2
3
4
5
6
7
abstract class baseClass
{
    public string haystack; // строка, в которой ведется поиск
    public string needle; // входная строка
    abstract public string searchString(); // метод для поиска
 
}


Кликните здесь для просмотра всего текста
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
class KMP : baseClass
{
    public KMP(string haystack, string needle)
    {
        this.haystack = haystack;
        this.needle = needle;
    }
 
    public override string searchString()
    {
        string nom = ""; //Объявление строки с номерами позиций
        if (needle.Length > haystack.Length) return nom; //Возвращает 0 поиск если образец больше исходной строки
        //Вызов префикс-функции
        int[] d = PrefFunc(needle);
        int i = 0, j;
        while (i < haystack.Length)
        {
            for (i = i, j = 0; (i < haystack.Length) && (j < needle.Length); i++, j++)
                while ((j >= 0) && (needle[j] != haystack[i]))
                    j = d[j];
            if (j == needle.Length)
                nom = nom + Convert.ToString(i - j) + ", ";
        }
        if (nom != "")
        {
            nom = nom.Substring(0, nom.Length - 2); //Удаление последней запятой и пробела
        }
        return nom; //Возвращение результата поиска
    }
    
    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;//Возвращение префикс-функции
    }
}


Кликните здесь для просмотра всего текста
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
82
83
84
85
86
87
88
89
90
91
class BM : baseClass
{
    public static char[] symbolOfNeedle; //Таблица символов входной строки  
    public static int[] valueShift; //Таблица смещений для символов
 
    public BM(string haystack, string needle)
    {
        this.haystack = haystack;
        this.needle = needle;
    }
    
    public override string searchString()
    {
        bool has, have; //Флаги
        int l, j, i; //Счетчики
        shiftBM(needle); //Вызов процедуры, формирубщей таблицу смещений
        string nom = ""; //Строка с номерами вхождений
        if (needle.Length > haystack.Length) return nom;
        //Основной цикл по исходной строке
        for (i = 0; i < haystack.Length - needle.Length + 1; i++)
        {
            j = needle.Length - 1;
            have = true;
            //Проверка с последнего символа                
            while ((j >= 0) && (have == true))
            {
                //Если не совпадает символ искомой и исходной
                if (haystack[i + j] != needle[j])
                {
                    have = false;
                    //Если это последний символ
                    if (j == needle.Length - 1)
                    {
                        l = 0;
                        has = false; //Флаг
                        //Поиск символа в таблице смещений
                        while ((l < needle.Length) && (has == false))
                        {
                            //Если символ есть
                            if (haystack[i + j] == symbolOfNeedle[l])
                            {
                                has = true; //Изменение флага
                                i = i + valueShift[l] - 1; //Сдвиг на величину
                            }
                            l++;
                        }
                        //Если не найден символ в таблице смещений
                        if (has == false)
                            //Сдвиг на величину искомой строки
                            i = i + needle.Length - 1;
                    }
                }
                j--;
            }
            if (have == true)
                nom = nom + Convert.ToString(i) + ", ";
        }
        //Если строка номеров не пустая
        if (nom != "")
        {
            nom = nom.Substring(0, nom.Length - 2); //Удаление последней запятой и пробела
        }
        return nom; //Возвращение результата поиска
    }
 
    public static void shiftBM(string x) //Процедура - формирование смещений
    {
        int j; //Счетчик
        int k = 0; //Счетчик
        bool fl; //Флаг
        symbolOfNeedle = 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 (symbolOfNeedle[j] == x[i]) fl = true;
                j++;
            }
            if (fl == false)
            {
                symbolOfNeedle[k] = x[i];
                valueShift[k] = x.Length - i - 1;
                k++;
            }
        }
    }
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.12.2013, 23:48
Ответы с готовыми решениями:

Написать метод поиска позиции вхождения подстроки тремя способами
Написать метод тремя различными способами: возвращаемое значение оформить с помощью 1) return, 2)...

Написать программу для поиска совершенных чисел
Здравствуйте уважаемые форумчане. Учитель задал написать программу для поиска совершенных чисел....

Написать программу для поиска в заданном массиве В, состоящем из 10-ти элементов, третьего положительного
Написать программу для поиска в заданном массиве В, состоящем из 10-ти элементов, третьего...

Создание регулярного выражения для поиска подстроки
Никак не получается написать корректно регулярное выражение. Задание: найти все строки,содержащие...

Написать программу сравнения двух введенных с клавиатуры чисел
Приветствую дорогих форумчан! Вы уже помогли выполнить одну задачу из практики, язык которой мы не...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.12.2013, 23:48

Написать программу, которая удаляет из строки все подстроки, состоящие из цифр
Дополнительное задание звучит так: Если принять во внимание, что &quot;подстрокой&quot; можно считать...

Написать программу для сравнения двух строк символов
Результат должен быть &quot;больше&quot;,&quot;меньше&quot;,&quot;равно&quot;(сравнение лексикографическое - сначала по первой...

Написать программу, предназначенную для сравнения двух строк
Написать программу, предназначенную для сравнения двух строк. (Строка считается большой, если при...


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

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

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