题解Week6
四月 14, 2022
7-1
给定一个字符串 text 和一个模式串 pattern，求 pattern 在text 中的出现次数。text 和 pattern 中的字符均为英语大写字母或小写字母。text中不同位置出现的pattern 可重叠。
KMP（都写在标题里了）
下面两个视频帮助了我很多。
1 |
|
7-2
众所周知，互联网时代以来各大公司被“脱裤”的历史是一部五彩缤纷（误）的血泪史，给各大厂商造成了极大的经济损失。更为重要的是，由于有些用户在多个网站使用相同的用户名、密码，一旦一家网站被拖库，用户往往会遭受全方位的损失。为避免此情况，良心企业一般只在数据库中存储用户密码的哈希值——也就是根据特定规则产生的散列值，无法由此倒推出原密码。但这种方法也有一个缺点，即输入不同的密码有极小概率会得到一样的哈希值（我们称之为碰撞），从而被系统认定密码正确！现在你所在的公司采取如下方法产生密码字符串（长度至少为8，只包含大小写字母和数字）的哈希值：
- 不区分字母的大小写，沿用16进制A代表10，B代表11……的规律，将原字符串视为一串36进制的数字
- 将字符串平均划为4块，若无法平均划分，保证在前的分块不短于在后的分块，且长度差不超过1。如：长度26的字符串各分块长度为7、7、6、6，长度13的字符串各分块长度为4、3、3、3
- 将每块的数字加和，取其个位数，四块取出的四个36进制数字顺次连接，得到一个四位36进制数字，即为该密码字符串的哈希值。
然而由于这种方式过于睿智，使得碰撞的几率奇高，你的任务就是为公司防范风险，在碰撞发生的时候给予示警！
这道题按照题目要求一步一步来即可。
首先要将密码打碎成三部分
1
2
3
4
5
6
7
8void breakstring(int n){//分成4部分的各部分长度
s1=s2=s3=s4=n/4;
n=n-s1*4;
if(n>0) {s1++;n--;}
if(n>0) {s2++;n--;}
if(n>0) {s3++;n--;}
return;
}再把一个字符转化为36进制（我这种方法过于麻烦）
1
2
3
4
5
6
7
8
9
10int turn10(char n){
if(n>='0'&&n<='9') return (int)(n-'0');
else if(n>='a'&&n<='z') return (int)(n-'a')+10;
else if(n>='A'&&n<='Z') return (int)(n-'A')+10;
}
char turn36(int n){
if(n>=0&&n<=9) return (char)(n+'0');
else if(n>=10&&n<=35) return (char)(n-10+'a');
else return turn36(n-36);
}通过上面两个（三个）函数计算一串字符的哈希。
1 | string Hashing(string str){ |
- 最后再做主程序即可。
- 下面是我极为复杂的代码。
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
using namespace std;
int s1,s2,s3,s4;
struct users{
string name;
string passwd;
string hash;
};
vector<users> usersdata;
void breakstring(int n){
s1=s2=s3=s4=n/4;
n=n-s1*4;
if(n>0) {s1++;n--;}
if(n>0) {s2++;n--;}
if(n>0) {s3++;n--;}
return;
}
int turn10(char n){
if(n>='0'&&n<='9') return (int)(n-'0');
else if(n>='a'&&n<='z') return (int)(n-'a')+10;
else if(n>='A'&&n<='Z') return (int)(n-'A')+10;
}
char turn36(int n){
if(n>=0&&n<=9) return (char)(n+'0');
else if(n>=10&&n<=35) return (char)(n-10+'a');
else return turn36(n-36);
}
string Hashing(string str){
string num="0000";
int bnum=0;
if(str.size()<=4) return str;
breakstring(str.size());
int i=0;
for(i=0;i<s1;i++){
bnum+=turn10(str[i]);
}
num[0]=turn36(bnum);
bnum=0;
for(;i<s1+s2;i++){
bnum+=turn10(str[i]);
}
num[1]=turn36(bnum);
bnum=0;
for(;i<s1+s2+s3;i++){
bnum+=turn10(str[i]);
}
num[2]=turn36(bnum);
bnum=0;
for(;i<str.size();i++){
bnum+=turn10(str[i]);
}
num[3]=turn36(bnum);
return num;
}
int main(){
/*
string str;
cin >> str;
cout << Hashing(str) << endl;
*/
int abc;
cin >> abc;
char operation;
string name,password;
bool repeated;
for(int i=1;i<=abc;i++){
cin >> operation;
repeated=false;
if(operation=='R'){
cin >> name >> password;
for(int i=0;i<usersdata.size();i++){
if(name==usersdata[i].name){
cout << "Repeated!" << endl;
repeated=true;
break;
}
}
if(!repeated){
users newuser;
newuser.name=name;
newuser.passwd=password;
newuser.hash=Hashing(password);
usersdata.push_back(newuser);
cout << "Signed!" << endl;
}
}
if(operation=='L'){
cin >> name >> password;
users compareduser;
for(int i=0;i<usersdata.size();i++){
if(name==usersdata[i].name){
compareduser=usersdata[i];
break;
}
}
if(password==compareduser.passwd){
cout << "Success!" << endl;
}
else{
if(Hashing(password)==compareduser.hash) cout << "Attention!" << endl;
else cout << "Failed!" << endl;
}
}
}
return 0;
}
7-3
分别输入两个字符串A和B，A由多个小字符串组成（中间由非字母隔开），B是由字母组成的字符串。求出A中包含B的小字符串的个数（详细看样例），并且输出它。（不区分大小写）
这也是一个KPM，直接照抄7-1，唯一的改动就是要把一串字符串给打碎分出来。
1 | while(true){ |
1 |
|
查看评论