В данном тексте найти наиболее часто встречающуюся последовательность символов максимальной длины

12 мая 2009

Для написания программы, которая будет искать в тексте последовательность символов максимальной длины, встречающуюся чаще всех остальных последовательностей, необходимо составить историю действий. Программа будет делить строку на равные части, сначала на 2, потом на 3 и так до длины строки, и сравнивать первую часть последовательности со второй.

Например, строку “aabb” при делении на 2 получаем две последовательности: “aa” и “bb”, затем “aa” сравниваем с “bb”. Если первая последовательность равна второй, то указываем, что последовательность “aa” встречается в тексте 2 раза, иначе 1 раз. В данном случае “aa” встречается 1 раз. В конце выполняем поиск из последовательностей символов, которые встречаются наиболее часто, и выбираем последовательность максимальной длины.
Запоминать последовательности и количество вхождений этих последовательностей будем в структуре, создадим ее:

public struct Symbols {
	string words;
	int kolvo;

	public Symbols(string w, int k)	{
		words = w;
		kolvo = k;
	}
	public string Words	{
		get { return words; }
		set { words = value; }
	}
	public int Kolvo {
		get { return kolvo; }
		set { kolvo = value; }
	}
};

Чтобы не добавлять в структуру одинаковые последовательности, напишем функцию, которая будет возвращать логическую “ложь” в том случае, если последовательность уже имеется в структуре:

Boolean Not_Eq_str(string c, Symbols[] sym, int k) {
	for (int i = 0; i < k; i++)
		if (sym[i].Words == c)
			return false;
			
	return true;
}

Еще одна важная функция, которая будет искать в уже сформированной структуре из последовательностей и их вхождению в текст ту последовательность, которая чаще встречается и длиннее всех остальных последовательностей. Функция выводит каждую последовательность в текстовое поле “richTextBox1” и возвращает индекс найденной последовательности.

int search(Symbols[] sym, int k) {
	int max = 0, max_len = 0, index = 0;
	for (int i = k - 1; i >= 0; i--) {
		richTextBox1.Text += sym[i].Words + " - " + sym[i].Kolvo + "\n";
		if (max < sym[i].Kolvo && max_len <= sym[i].Words.Length) {
			max = sym[i].Kolvo;
			max_len = sym[i].Words.Length;
			index = i;
		}
	}
	return index;
}

И, наконец, процедура обработки события нажатия на кнопку “button1”:

private void button1_Click(object sender, EventArgs e)
{

Открываем диалог для открытия текстового файла, очищаем поле “richTextBox1”, в строку “stroka” записываем текст из выбранного файла, получаем его длину и инициализируем структуру:

openFileDialog1.ShowDialog();
string p = openFileDialog1.FileName;
StreamReader inStream = new StreamReader(p);
patch.Text = p;
richTextBox1.Clear();
string s = "";
string stroka = "";

while ((s = inStream.ReadLine()) != null) {
	stroka += s;
}
int i, l = stroka.Length, n = 0;

Symbols[] sym = new Symbols[l];
int j, k = 0, x;
string subs = "";

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

if (l == 1) {
	symbols.Text = stroka;
	kolvosym.Text = "1";
	return;
}

Добавляем в структуру весь текст и количество вхождений указываем равным 1:

sym[k].Words = stroka;
sym[k].Kolvo = 1;
k++;

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

for (i = 2; i < l; i++) {
	if (l % i == 0)	{
		int c = l / i;
		for (j = 0; j < i; j++)	{
			subs = stroka.Substring(j * c, c);
			x = 0;
			for (int a = 0; a < i; a++)	{
				if (stroka.Substring(a * c, c) == subs)
					x++;
			}
			
			if (Not_Eq_str(subs, sym, k)) {
				sym[k].Words = subs;
				sym[k].Kolvo = x;
				k++;
			}
		}
	}
}
n = k;

Получаем индекс в структуре, где находится наиболее часто встречающуюся последовательность символов максимальной длины, выводим ее и количество вхождений ее в текст в поля на форму приложения:

int ind = search(sym, k);
symbols.Text = sym[ind].Words;
kolvosym.Text = Convert.ToString(sym[ind].Kolvo);
}

Это, конечно, не самый хороший алгоритм, который дает быстрое выполнение программы, но главное же, что он работает.

Автор: Евтеев Евгений Александрович