最近做一個(gè)東西正好需要生成字典的算法，類似一些密碼字典生成器(主要運(yùn)用在暴力破解)。生成的密碼會(huì)根據(jù)密碼長(zhǎng)度與字典集合的長(zhǎng)度成指數(shù)關(guān)系。
可以用一個(gè)函數(shù)來表示
f( x , y ) = x ^y ; x表示我們要生產(chǎn)的密碼長(zhǎng)度，y表示我們要生成的密碼字典字符集合。
當(dāng)時(shí)想到就有3個(gè)算法。
1.循環(huán)
關(guān)于循環(huán)，可以參考水仙花數(shù)的多層嵌套求解，主要算法如下:
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 * 幾位密碼就嵌套幾層循環(huán)
16
*/
17
18 }
19 }
20
}
這種方式移植不好，而且代碼臃腫。
2.遞歸
做過字符串的全排列的都明白這個(gè)算法，這種也是基于這種方式：但是由于隨著字典集合或者密碼長(zhǎng)度的增加，很容易會(huì)出現(xiàn)堆棧的內(nèi)存溢出。
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種方法的不錯(cuò)，然后寫了一個(gè)非遞歸的算法
主要借用橫向掃描的方式，借鑒一個(gè)數(shù)組來進(jìn)行記錄當(dāng)前應(yīng)該生成的密碼。
主要算法如下:
1/**//*
2* 生成字典的函數(shù)
3* @parm 需要生成的長(zhǎng)度
4*/
5void MakeDict( int Len )
6{
7 char Dict[MaxDictLen+1]; // 生成的字典字符串
8 int Array[MaxDictLen]; // 記錄當(dāng)前應(yīng)該生成字典數(shù)組
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 /**//// 字典數(shù)組坐標(biāo)更新
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}
附上第三個(gè)生成算法源碼:
link