勤能补拙,Expter

成都游戏Coder,记录游戏开发过程的笔记和心得!

一个字典生成算法几种解法:

        最近做一个东西正好需要生成字典的算法,类似一些密码字典生成器(主要运用在暴力破解)。生成的密码会根据密码长度与字典集合的长度成指数关系。
       可以用一个函数来表示
        f( x , y  )  = x ^y ;           x表示我们要生产的密码长度,y表示我们要生成的密码字典字符集合。

      当时想到就有3个算法。
      
    1.循环
         关于循环,可以参考水仙花数的多层嵌套求解,主要算法如下:

 1/// Dict 为生成的密码 , g_Dict为字典集合
 2for ( 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

posted on 2009-11-08 00:56 expter 阅读(3291) 评论(1)  编辑 收藏 引用 所属分类: 其他学习笔记算法与数据结构

评论

# re: 一个字典生成算法几种解法: 2014-05-11 22:28 张晶

memset是什么  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理