CS50 pset2

上上一周开始了哈佛大学的CS50课程学习,这周在解决pset2中的crack时候花了挺多时间,这里专门总结下。

题目地址

这题的关键问题是把长度小于等于n的并且由大小写字母组成的字符串穷举出来,但是代码有个小问题,如果我取m=6,那么程序运行会报错,感觉是空间太大的或者循环太久原因,代码如下。

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
#define _XOPEN_SOURCE
#include <unistd.h>
#include <stdio.h>
#include <cs50.h>
#include <string.h>
#include <math.h>

//数字字母个数25*2 = 52
const int K = 52;
//数组长度
const int M = 5E8;
//最长长度+1
const int m = 5;
//存放单词的数组,注意第二个维度长度为m+1
char words[M][5];

//获得大小写字符
void getcharacter(char c[]);
//获得单词,全存在一个数组里,start到end为长度为l的字符,返回长度l+1的起始处
int getword(char word[][m], int start, int end, char c[], int l);
//将字符s第一位添加c,存入word中,例如a,pple变为apple
void helper(char c, char s[], char word[]);

int main(int argc, string argv[]){
char salt[3];
string hash;
//error
if(argc != 2){
printf("Usage: ./crack hash\n");
return 1;
}else{
//获得salt
salt[0] = argv[1][0];
salt[1] = argv[1][1];
salt[2] = '\0';
hash = argv[1];
}

//获得大小写字符
char c[K];
getcharacter(c);

//获得长度为1的单词
getword(words, 0, 0, c, 1);
int start = 0;
int end = K-1;
//获得其余长度的单词
for(int i=2; i<m; i++){
int temp = getword(words, start, end, c, i);
start = end+1;
end = temp;
}

//验证
for(int i=0; i<end; i++){
string Hash = crypt(words[i], salt);
if(strcmp(Hash, hash) == 0){
printf("%s\n", words[i]);
break;
}
}

return 0;
}


void getcharacter(char c[]){
int cnt = 0;
for(int i=0; i<26; i++,cnt++){
c[cnt] = 'a' + i;
}

for(int i=0; i<26; i++,cnt++){
c[cnt] = 'A' + i;
}
}

int getword(char word[][m], int start, int end, char c[], int l){
if(l == 1){
for(int i=0; i<K; i++){
char newword[2];
newword[0] = c[i];
newword[1] = '\0';
strcpy(word[i], newword);
}
return K;
}else{
int cnt = 1;
for(int i=start; i<=end; i++){
for(int j=0; j<K; j++){
char newword[l+1];
helper(c[j], word[i], newword);
strcpy(word[end+cnt], newword);
cnt++;
}
}
return end+cnt-1;
}
}


void helper(char c, char s[],char word[]){
int n = strlen(s) + 2;
word[n-1] = '\0';
word[0] = c;
for(int i=1; i<n-1; i++){
word[i] = s[i-1];
}
}

这里列出几个注意的点

  1. 利用二维字符数组char words[M][5]来存储长度小于等于n的字符串,注意由于M比较大,所以最好写在main函数之前。
  2. 为了求出长度小于等于n的全部字符串,分别求出长度为1,2,…n的字符串,利用长为i的字符串求出长度为i+1的字符串,用start表示长度为i的字符的起始位置,end表示长度为i的字符的结束位置,然后做二重循环,先遍历长度为i的字符,再遍历全部大小写字母,利用helper函数将单个字母添加到长度为i的字符上,构成长度为i+1的字符。
  3. 字符拷贝的时候一定要用strcpy函数,如果用等于号会出问题。