Поиск подстроки в строке
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
о поиска
s.Length)returnnom;"> if (x.Length > s.Length) return nom;
//Цикл по исходной строке
for (int i = 0; i < s.Length - x.Length+1; i++)
{
bool flag = true; //Флаг
int 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) + ", ";
}
//Если вхождение найдено
if (nom != "")
{
//Удаление последней запятой и пробела
nom = nom.Substring(0, nom.Length - 2);
}
//Возвращение результата поиска
return nom;
}
Приложение Б
Реализация алгоритма Рабина-Карпа
//Хеш-функция для алгоритма Рабина-Карпа
public static int Hash(string s)
{
int rez = 0;
for (int i = 0; i < s.Length; i++)
{
rez += (int)(s[i]);//Сложение кодов букв
}
return rez;
}
//Функция поиска алгоритмом Рабина
public static string Rabina(string x, string s)
{
string nom = "";
//Если искомая строка больше исходной - возврат пустого поиска
s.Length)returnnom;"> if (x.Length > s.Length) return nom;
//Вычисление хеш-функции искомой строки
int xhash = Hash(x);
//Вычисление хеш-функции первого слова длины образца в строке S
int shash = Hash(s.Substring(0,x.Length));
for (int i = 0; i < s.Length - x.Length; i++)
{
//Если значения хеш-функций совпадают
if (xhash == shash)
{
bool flag = true; //Флаг
int 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) (s[i]) +
(int)(s[i + x.Length]);
}
//Если вхождение найдено
if (nom != "")
{
nom = nom.Substring(0, nom.Length - 2);
}
return nom;
}
Приложение В
Реализация алгоритма Кнута-Морриса-Пратта
//Префикс-функция для КМП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;//Возвращение префикс-функции
}
//Функция поиска алгоритмом КМПstatic string KMP(string x, string s)
{
//Объявление строки с номерами позиций
string nom = "";
s.Length)returnnom;"> if (x.Length > s.Length) return nom;
//Вызов префикс-функции
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;
}
Приложение Г
Реализация алгоритма Бойера-Мура
//Таблица символов искомой строки static char[] SymbolOfX;
//Таблица смещений для символов static int[] ValueShift;
//Процедура - формирование смещенийstatic void ShiftBM(string x)
{
int j;//Счетчик
int k = 0;//Счетчик
bool fl;//Флаг
SymbolOfX = new char[x.Length];//Инициализация
ValueShift = new int[x.Length];//Инициализация
//Цикл по искомой строке без последнего символа
=0;i--)"> 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++;
}
}
}
//Функция поиска алгоритмом БМstatic string BM(string x, string s)
{
bool has, have;//Флаги
int l,j,i;//Счетчики
//Вызов процедуры, формирубщей таблицу смещений
Function.ShiftBM(x);
//Объявление строки с номерами позиций
string nom = "";
s.Length)returnnom;"> if (x.Length > s.Length) return nom;
//Основной цикл по исходной строке
for (i = 0; i < s.Length-x.Length+1; i++)
{
j = x.Length - 1;
have = true;
//Проверка с последнего символа ((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;//Возвращение результата поиска
}
Приложение Д
Реализация программного кода программы
Код формы:
System;System.Collections.Generic;System.ComponentModel;System.Data;System.Drawing;System.Linq;System.Text;System.Windows.Forms;System.IO;Fuction;System.Diagnostics;System.Threading;
KurgachevND_Kursovaya_1kurs
{
public partial class Form1 : Form
{
public static string str,//Объявление исходной строки