最长递增子序列
线性时间求解最大回文字串

字符串全排序

Jimmy posted @ 2011年10月17日 01:43 in Others , 1921 阅读

给定一个字符串,由小写字母升序排列,且各不相同,输出这个字符串的全排列(字典序),这个程序会超过一秒,主要是生成全排列部分的算法有问题不能做到输出有序,生成全排列之后不得不使用快速排序,因而会超时。更优化的算法进行中……

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 7

int counter = 0;
char array[1000][MAXSIZE];

int compare(const void *s1, const void *s2)
{
    char *a, *b;
    a = (char*)s1;
    b = (char*)s2;
    return strcmp(a, b);
}

void arrange(char *s, int start, int end)
{
    int i;
    char tmp;
    if(start == end)
    {
	strcpy(array[counter], s);
	counter++;
    }
    else
    {
	for(i=start; i<end; i++)
	{
	    tmp = s[start];
	    s[start] = s[i];
	    s[i] = tmp;
	    arrange(s, start+1, end);
	    tmp = s[start];
	    s[start] = s[i];
	    s[i] = tmp;
	}
    }
}

int main()
{
    char str[MAXSIZE];
    int i;
    while(scanf("%s",str) != EOF)
    {
        counter = 0;
 	arrange(str, 0, strlen(str)); 
        qsort((void*)array, counter, sizeof(char[MAXSIZE]),compare);
        //printf("counter = %d\n",counter);
    	for(i=0; i<counter; i++)
	    printf("%s\n",array[i]);
    }
    return 0;
}

 

Avatar_small
scturtle 说:
2011年10月17日 18:03

生成全排列后加到字典树里然后dfs输出?


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter