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

Алгоритм Кнута-Морриса-Пратта (КМП)

12.11.2017, 14:30. Просмотров 612. Ответов 4
Метки нет (Все метки)

Здравствуйте, мне необходима помощь в реализации алгоритма кмп в рамках поиска подстроки в строке, когда искомых подстрок может быть несколько. Я понимаю саму суть алгоритма, но не знаю, как реализовать именно для подстроки, когда там несколько символов, а не один.
Например:
исходная строка - aabaabaaacaabb
искомая подстрока: aabaa
Результатом должны быть индексы начала вхождения. Ну или как-нибудь иначе, не знаю.

Добавлено через 2 часа 5 минут
Есть вот такой вот код:
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
 private int[] arrPrefix;
        private int intCounter = 0;
        private int[] GetPrefixFunction(string strPattern)
        {
            int[] result = new int[strPattern.Length - 1];
            result[0] = 0;
            for (int i = 1; i <= strPattern.Length - 1; i++)
            {
                int k = result[i - 1];
                while (k > 0 && strPattern[k] != strPattern[i])
                {
                    k = result[k - 1];
                }
                if (strPattern[k] == strPattern[i])
                    k += 1;
                result[i] = k;
            }
            return result;
        }
        public int FindSubstring(string strInput, string strPattern)
        {
            int intInputLen = strInput.Length;
            int intPatternLen = strPattern.Length;
            int i;
            int j;
            bool blnFlag;
            if (intInputLen == 0 | intPatternLen == 0)
                return -2;
            arrPrefix = GetPrefixFunction(strPattern);
            j = 0;
            for (i = 1; i <= intInputLen; i++)
            {
                blnFlag = false;
                while (j > 0 && strPattern[ j + 1] != strInput [i])
                {
                    j = arrPrefix[j - 1];
                    intCounter += 1;
                    blnFlag = true;
                }
                if (blnFlag == false)
                    intCounter += 1;
                if (strPattern[j + 1] == strInput[i])
                {
                    j += 1;
                }
                if (j == intPatternLen)
                {
                    return i - intPatternLen;
                }
            }
            return -1;
        }
Но там появляется ошибка, что индекс находится вне границ массива. И вообще я не уверена, что там получится найти несколько одинаковых подстрок
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.11.2017, 14:30
Ответы с готовыми решениями:

Алгоритм Кнута - Морриса - Пратта
Доброго времени суток. Помогите,пожалуйста, написать программу поиска подстроки...

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

Алгоритмом мягкого переноса Ляна-Кнута
Добрый день! Я пытаюсь разобраться с алгоритмом мягкого переноса Ляна-Кнута...

Алгоритм Кнута, Морриса и Пратта (КМП)
Реализовать алгоритм Кнута, Морриса и Пратта для поиска, вводимого с клавиатуры...

Алгоритм КМП(Кнута-Морриса-Пратта )
нужно с помощью алгоритма КМП найти первое вхождение одной числовой...

4
Woldemar89
TheGreatCornholio
1207 / 688 / 279
Регистрация: 30.07.2015
Сообщений: 2,356
Завершенные тесты: 1
12.11.2017, 18:55 2
0
Diamante
1313 / 1031 / 652
Регистрация: 14.08.2016
Сообщений: 3,584
Завершенные тесты: 1
13.11.2017, 00:48 3
ну входные данные ясны... что должно быть на выходе и что из методов можно пользовать?
З.Ы. по ошибкам поможет отладчик
0
Pawn_AB
0 / 0 / 0
Регистрация: 18.10.2017
Сообщений: 5
16.12.2017, 11:32  [ТС] 4
Здравствуйте, помогите доделать код для алгоритма кмп с повторениями подстроки в строке. Код найден на форуме, но почему-то выскакивает ошибка, о выходе за границы массива(Result)
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
using System;
using System.IO;
 
namespace justForFun
{
    class MainClass
    {
        public static void Main (string[] args)
        {
            Console.WriteLine( "Input filepath and press enter" );
            string filePath = Console.ReadLine();
            Console.WriteLine( "Input searched string" );
            string pattern = Console.ReadLine();
            
            string text = "";
            try
            {
                text = File.ReadAllText( filePath );
            }
            catch( FileNotFoundException exception )
            {
                Console.WriteLine("File " + filePath + " not found" );
                Console.ReadLine();
                return;
            }
            
            try
            {
                int position = FindSubstring( text, pattern );
                Console.WriteLine(position);
            }
            catch(ArgumentException exception)
            {
                Console.WriteLine(exception);
            }
            Console.ReadLine();
        }
 
        private static int FindSubstring (string input, string pattern)
        {
            int n = input.Length;
            int m = pattern.Length;
            if (0 == n)
                throw new ArgumentException ("String mustn't be empty", "input");
            if (0 == m)
                throw new ArgumentException ("String mustn't be empty", "pattern");
            
            int[] d = GetPrefixFunction (pattern);
            
            int i, j;
            for (i = 0,j = 0; (i < n) && (j < m); i++,j++)
                while ((j >= 0) && (pattern[j] != input[i]))
                    j = d[j];
            
            if (j == m)
                return i - j;
            else
                return -1;
        }
 
        private static int[] GetPrefixFunction (string pattern)
        {
            int length = pattern.Length;
            int[] result = new int[length];
            
            int i = 0;
            int j = -1;
            result[0] = -1;
            while (i < length - 1) {
                while ((j >= 0) && (pattern[j] != pattern[i]))
                    j = result[j];
                i++;
                j++;
                if (pattern[i] == pattern[j])
                    result[i] = result[j];
                else
                    result[i] = j;
            }
            return result;
        }
    }
}
0
Pawn_AB
0 / 0 / 0
Регистрация: 18.10.2017
Сообщений: 5
16.12.2017, 11:38  [ТС] 5
На выходе должны быть индексы начала вхождения искомой подстроки. Но подстрока может повторяться.
0
16.12.2017, 11:38
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.12.2017, 11:38

Алгоритм Кнута-Морриса-Пратта
Здравствуйте. Есть задание в котором необходимо найти вхождения подстроки в...

Алгоритм Кнута, Морриса и Пратта
Ребята, помогите пожалуйста!!! Задали написать программу, пыталась сама...

Алгоритм Кнута, Морриса и Пратта
//описание функции алгоритма Кнута, Морриса и Пратта int KMPSearch(char...


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

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

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