不看会后悔的Windows XP之经验谈	简单快捷DIY实用家庭影院

由给定字符串生成新字符串

楼主louislingjjw（J2W）2002-09-22 10:49:46 在专题开发/技术/项目 / 数据结构与算法提问

各位大哥，帮我看看这道题目，这道题目应该怎么做呢？

在任意给定的字符串(如'123')上，生成所有由该字符串上的字符组成，并且包含n个字符字符串，
要求：生成的字符串中不存在相同的两个相邻子字符串。

例如：
输入：字符串 '123' 整数 5
输出：字符串: '12321','21312'...

(不正确的子字符串如: '12323' ,因为有相邻子字符串'23' )
问题点数：87、回复次数：10Top

1 楼one_add_one（)我要睡觉：）回复于 2002-09-22 22:41:04 得分 7

搜索。。Top

2 楼howie（flying fox）回复于 2002-09-22 23:07:30 得分 0

输出所有可能的字符串吗？
‘123’：5
那不是有405种可能？相邻子字符串就只有‘11’‘22’‘33’‘1212’‘2323’五种共约296种可能错误排列
这个分析起来……想不出
建立一个相邻子字符串集合，再由给定字符串取出所有不同字符生成所有可能串，再查找匹配？
似乎太麻烦了吧…………Top

3 楼one_add_one（)我要睡觉：）回复于 2002-09-22 23:33:05 得分 10

#include <stdio.h>
#include <string.h>

int check[127][127];
char str[50];
char result[200];
int l;

search(int k){
int i;
if (k<=0){
printf("%s\n",result);
return;
}
for (i=0;i<strlen(str);i++){
if (k<l){
if (!check[result[l-k-1]][str[i]]){
check[result[l-k-1]][str[i]]=1;
result[l-k]=str[i];
search(k-1);
check[result[l-k-1]][str[i]]=0;
}
}
else{
result[l-k]=str[i];
search(k-1);
}
}
}

main(){
int i,j;

for (i=0;i<127;i++)
for (j=0;j<127;j++)
check[i][j]=0;

scanf("%s",str);
scanf("%d",&l);
result[l]='\0';

search(l);
}Top

4 楼louislingjjw（J2W）回复于 2002-09-23 11:55:21 得分 0

参考答案我有，关键是思路，或者能给程序加点注释说明一下吗？
我刚刚学，在看程序员的书，可是很多不明白！
先谢谢大家了！Top

5 楼xdspower（杂食菜熊）回复于 2002-09-23 12:13:03 得分 10

输出所有可能的字符串吗？
‘123’：5
那不是有405种可能？相邻子字符串就只有‘11’‘22’‘33’‘1212’‘2323’五种共约296种可能错误排列
这个分析起来……想不出
建立一个相邻子字符串集合，再由给定字符串取出所有不同字符生成所有可能串，再查找匹配？
似乎太麻烦了吧…………
－－－－－－－－－－－－－－－－－－－－－－－
上面有错误，还有"1313","3131","2121","3232"等...
我觉得要注意的是生成所有由该字符串上的“字符”组成这个条件，这转换后就是先要在字符串中抽取出所有的字符，然后就是生成要求的字符串，然后就是子串的处理了，这时就要把生成的字符串中的所有子串（包括单个字符的子串）取出来进行条件检测，由于子检测有没有相邻，最大子串就是不超过总长的一半的字符串（考虑计算中会出现半个字符问题），然后比较同长邻串就可以判断了。
不过结果是比较多的！！！！！！
Top

6 楼louislingjjw（J2W）回复于 2002-09-23 22:19:47 得分 0

xdspower，谢谢你的关注，
你好象理解错了意思吧，如果输入'123' 5
那么题目意思是：生成的字符串是5位，你说的11’‘22’‘33’‘1212’‘2323’都不到5位，无位是指从'123'的字符中挑选字符，可以重复，生成的字符要是5个字符长，比如 12321，12123这些都是符合要求的，如果12323就不符合了，因为有了相同的相邻的子字符串“23”

这是程序员的书上的题目，我看了答案但是不太明白，请大家帮忙解释一下！Top

7 楼howie（flying fox）回复于 2002-09-23 23:32:01 得分 50

有一点想说一下，我觉得不是5位或者几位的问题，只要包含‘11’‘1212’的就是不正确的，因为‘1’是它的子串。还有，‘12123’应该也是不对的，‘1212’就是连续的两个子串。如果这些都算的话，对于五位的，似乎只有‘12323’和‘1233X’是错误的了，那情形就好判断多了。
我觉得如果只是要得到这样的串的话，大可以做一个表。
字符串a（0）……a（n），在生成的串中，字符a（i）之后为
a（0）—a（i）的时候才有可能出现相邻的子串，那满可以从a（i+1）以后的里面选一个，跟在a（i）后面，如此循环填加。
但这样得不到所有的可能串，只能有n！个
要得到所有的可能串，应该先得到所有可能相邻子串的组合，然后生成所有可能的目标串，再通过比照将所有含有相邻子串的组合的串删除，最后得到的就是了。Top

8 楼howie（flying fox）回复于 2002-09-23 23:38:04 得分 5

to xdspower()：
我觉得‘13’不是‘123’的子串，因为在‘123’中字符是有顺序的组成字符串，‘13’不能包括在‘123’的子串集里。字符串是一个sequence，而不仅仅是一个字符的set。Top

9 楼one_add_one（)我要睡觉：）回复于 2002-09-24 00:35:28 得分 5

int check[127][127];

是一个表，记录出现过的相邻的字符。。

然后递归搜索。把所有的情况搜一遍。。。打印出结果。。Top

10 楼xdspower（杂食菜熊）回复于 2002-09-25 08:44:14 得分 0

看来你是要求不要有“源串的子串”重复问题，这个是题目有歧义了，
这个就把最后的子串分离先在源串中进行，在再构建的串中搜索比较了，这个可能还真的不好办，Top