首页 > 代码库 > Generating Fast UVA 10098
Generating Fast UVA 10098
说说:
这道题的其实就是给你一个字符串,然后输出该字符串所含字符能构成的全部的串,并按字典升序输出。解法的话,无非就是递归实现。先将原字符串排序,然后逐一确定每个位置上的字符。为了防止有重复的字符串出现,每个位置上的字符不能与之前相同。具体的解释请参见刘汝佳的《算法竞赛入门经典》P118,生成可重集的排列。
源代码:
#include <stdio.h> #include <string.h> #define MAX 10+5 char s[MAX]; char p[MAX]; int N; void print_permutation(int); int main(){ int n,j,i; char c; // freopen("data","r",stdin); scanf("%d",&n); while(n--){ scanf("%s",s); N=strlen(s); p[N]='\0'; for(i=1;i<N;i++)//先将原字符串排序 for(j=i;j>0;j--) if(s[j]<s[j-1]){ c=s[j]; s[j]=s[j-1]; s[j-1]=c; } print_permutation(0); putchar('\n'); } return 0; } void print_permutation(int cur){ int i,j,c1,c2; if(cur==N){ printf("%s\n",p); return ; } for(i=0;i<N;i++) if(!i||s[i]!=s[i-1]){//保证所得字符串不重复 c1=c2=0; for(j=0;j<cur;j++) //统计当前字符在已生成的p中出现的次数 if(s[i]==p[j]) c1++; for(j=0;j<N;j++)//统计当前字符在s中出现的总次数 if(s[i]==s[j]) c2++; if(c1<c2){ p[cur]=s[i]; print_permutation(cur+1); } } return; }
Generating Fast UVA 10098
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。