最近做一个东西正好需要生成字典的算法，类似一些密码字典生成器(主要运用在暴力破解)。生成的密码会根据密码长度与字典集合的长度成指数关系。
可以用一个函数来表示
f( x , y ) = x ^y ; x表示我们要生产的密码长度，y表示我们要生成的密码字典字符集合。
当时想到就有3个算法。
1.循环
关于循环，可以参考水仙花数的多层嵌套求解，主要算法如下:
1
/**//// Dict 为生成的密码 ， g_Dict为字典集合 2
for ( int i = 0 ; i < Len ; i++ )
3
{
4
Dict[0] = g_Dict[i];
5
6 for ( int j = 0 ; j < Len ; j++)
7
{
8 Dict[1] = g_Dict[j];
9
10 for ( int k = 0 ; k < Len ; k++ )
11 {
12 Dict[2] = g_Dict[k];
13
14 /**//*
15 * 几位密码就嵌套几层循环
16
*/
17
18 }
19 }
20
}
这种方式移植不好，而且代码臃肿。
2.递归
做过字符串的全排列的都明白这个算法，这种也是基于这种方式：但是由于随着字典集合或者密码长度的增加，很容易会出现堆栈的内存溢出。
1void solve(int len,int p , int s,int n)
2{
3 int i;
4 if( s == n )
5 {
6 /**////std::cout << Dict << std::endl;
7 return ;
8 }
9 if(s>n||p>n)
10 return;
11 for( i=p ; i < len ; i++ )
12 {
13 solve(len,i+1,s+1,n);
14 }
15}
3.BFS
有了前2种方法的不错，然后写了一个非递归的算法
主要借用横向扫描的方式，借鉴一个数组来进行记录当前应该生成的密码。
主要算法如下:
1/**//*
2* 生成字典的函数
3* @parm 需要生成的长度
4*/
5void MakeDict( int Len )
6{
7 char Dict[MaxDictLen+1]; // 生成的字典字符串
8 int Array[MaxDictLen]; // 记录当前应该生成字典数组
9
10 memset( Array , 0 , sizeof(Array) );
11
12 bool bStop = true;
13
14 int i,j;
15 for ( ; bStop ; ) // 是否生成完毕
16 {
17 for ( i = 0 ; i < Len ; i++ )
18 {
19 Dict[i] = g_Dict[Array[i]];
20 }
21 Dict[Len] = '\0';
22
23 std::cout << Dict << std::endl;
24
25 /**//// 字典数组坐标更新
26 for ( j = Len - 1 ; j >= 0 ; j -- )
27 {
28 Array[j] ++ ;
29
30 if ( Array[j] != ((int)g_Dict.length()) )
31 {
32 break;
33 }
34 else
35 {
36 Array [j] = 0;
37 if( j == 0 ) // 生成完毕
38 bStop = false;
39 }
40 }
41 }
42}
附上第三个生成算法源码:
link