BF+KMP算法

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <iostream>
#include <string.h>
#define MaxSize 1000
#define MaxLen 1000
using namespace std;

struct SeqString
{
	char ch[MaxSize];
	int len;
};

// BF算法
int BF(char S[], char T[])
{
	int i = 0, j = 0, start = 0;
	while (S[i] != '\0' && T[j] != '\0')
	{
		if (S[i] == T[j])
		{
			i++;
			j++;
		}
		else
		{
			start++;
			i = start;
			j = 0;
		}
	}
	if (T[j] == '\0')
	{
		return start + 1;
	}
	else
	{
		return 0;
	}
}

void GetNext(SeqString t, int next[])
{
	int j, k;
	j = 0;
	k = -1;
	next[0] = -1;
	while (j < t.len - 1)
	{
		if (k == -1 || t.ch[j] == t.ch[k])
		{
			j++;
			k++;
			next[j] = k;
		}
		else
			k = next[k];
	}
}

int KMP(SeqString s, SeqString t)
{
	int next[MaxLen], i = 0, j = 0;
	GetNext(t, next); // 求next值
	while (i < s.len && j < t.len) // 修改这里
	{
		if (j == -1 || s.ch[i] == t.ch[j])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}
	if (j >= t.len)
	{
		return (i - t.len); // 返回下标
	}
	else
	{
		return 0; // 不匹配
	}
}

int main()
{
	cout << "*******BF算法实验*******" << endl;
	char a[MaxLen], b[MaxLen];
	cout << "请输入主串" << endl;
	cin >> a;
	cout << "输入了" << a << endl;
	cout << "请输入子串" << endl;
	cin >> b;
	cout << "输入了" << b << endl;
	int bf = BF(a, b);
	if (bf == 0)
	{
		cout << "BF算法结果：未找到" << endl;
	}
	else
	{
		cout << "BF算法结果：位置是：" << bf << endl;
	}
	cout << "*******BF算法实验*******" << endl;
	cout << endl;
	cout << endl;
	cout << endl;
	cout << "*******KMP算法实验*******" << endl;
	SeqString s, t;
	cout << "请输入主串" << endl;
	cin >> s.ch;
	s.len = strlen(s.ch);
	cout << "输入了" << s.ch << endl;
	cout << "长度是：" << s.len << endl;
	cout << "请输入子串" << endl;
	cin >> t.ch;
	t.len = strlen(t.ch);
	cout << "输入了" << t.ch << endl;
	cout << "长度是：" << t.len << endl;
	int kmp = KMP(s, t);
	if (kmp == 0)
	{
		cout << "KMP算法结果：未找到" << endl;
	}
	else
	{
		cout << "KMP算法结果：位置是：" << kmp + 1 << endl; // 返回的下标从1开始计数，所以需要+1
	}
	cout << "*******KMP算法实验*******" << endl;

	return 0; // 确保main函数有返回值
}

对称矩阵的压缩

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
#include <iostream>
#define MaxSize 1000
using namespace std;

struct yuansu
{
	int i;
	int j;
	int data;
};

class Matrix
{
public:
	Matrix();
	void PrintMatrix();
	void getMatrix(yuansu s);
	~Matrix();

private:
	int ma[MaxSize];
};

Matrix::Matrix()
{
	for (int i = 0; i < MaxSize; i++)
		ma[i] = 0;
}

Matrix::~Matrix()
{
}

void Matrix::getMatrix(yuansu s)
{
	if (s.i >= s.j) {
		int k = s.i * (s.i - 1) / 2 + s.j - 1;
		ma[k] = s.data;
	}
}

void Matrix::PrintMatrix()
{
	for (int i = 0; i < MaxSize; i++)
		if (ma[i] != 0)
			cout << "ma[" << i << "] = " << ma[i] << endl;
}

int main()
{
	Matrix ws;
	yuansu s;
	cin >> s.i >> s.j >> s.data;
	ws.getMatrix(s);
	ws.PrintMatrix();
	cin >> s.i >> s.j >> s.data;
	ws.getMatrix(s);
	ws.PrintMatrix();
	cin >> s.i >> s.j >> s.data;
	ws.getMatrix(s);
	ws.PrintMatrix();
	return 0;
}