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

谁能写出这个程序？

楼主FarAwayFromHome（）2006-12-01 22:46:50 在 Java / J2SE / 基础类提问

有一个字符串，比方说"abc"，编写一个函数，求出它的所有子串并打印出来，即:a,b,c,ab,ac,bc,abc还有空串,哪位高手能写个算法?欢迎各位有志于软件开发的朋友加入程序讨论群一起讨论:32998944(程序人生) 问题点数：20、回复次数：54Top

1 楼AWUSOFT（程序设计,一个字:爽!）回复于 2006-12-01 22:51:44 得分 0

穷举法呀...Top

2 楼AWUSOFT（程序设计,一个字:爽!）回复于 2006-12-01 22:59:31 得分 0

public ArrayList toSubString(String str)
{
ArrayList list = new ArrayList();
if(str != null)
{
int lenght=str.length();
list.add("");
for(int i=0;i<lenght;i++)
{
for(int j=i+1;j<lenght;j++)
{
list.add(str.substring(i,j));
}
}
}
return list;
}Top

3 楼FarAwayFromHome（）回复于 2006-12-01 23:09:07 得分 0

麻烦大侠能不能把ArrayList类的实现写出来？Top

4 楼tianwill（堕落疯子）回复于 2006-12-01 23:22:48 得分 0

看API吧。ArrayList的实现在里面。Top

5 楼AWUSOFT（程序设计,一个字:爽!）回复于 2006-12-01 23:37:20 得分 0

晕./.ArrayList的实现还要我写出来啊....这个可是Java提供给我们的呀Top

6 楼ly342540479（心不在跳了, 脸也不红了）回复于 2006-12-02 08:38:04 得分 0

学习,Top

7 楼haisenmai（我应该做得到）回复于 2006-12-02 10:15:52 得分 0

原始字符串应该不重复的吧？ aac这样的不考虑？
结果里面的 ab ba要过滤掉嘛？Top

8 楼benq998（问题没解决,坚决不结贴.解决了还不结贴,极度鄙视.）回复于 2006-12-02 10:22:54 得分 0

看来搂住的基础不一般阿，连ArrayList都不知道哪里来的，劝你有时间找java API文档看看，中文英文的都行，看看里面都有什么，干什么用的，不用你一定看会它到底怎么用，至少知道Java API都提供的什么功能，在需要用的时候时候能马上就找出来用就够了。Top

9 楼flyineagle（纸上得来终觉浅，绝知此事要躬行）回复于 2006-12-02 12:34:02 得分 0

ArrayList 的实现？这个问题比较严重。解释完了，恐怕还有list是怎么实现的。这一步步研究下去，那就是：java具体是怎么出来的。不错，值得深入研究。写个java++就靠这个了Top

10 楼diamondwjk（志摩）回复于 2006-12-02 16:35:14 得分 0

public ArrayList toSubString(String str) {
ArrayList<String> list = new ArrayList<String>();
if (str != null) {
int lenght = str.length();
list.add("");
for (int i = 0; i < lenght; i++) {
for (int j = i + 1; j < lenght; j++) {
list.add(str.substring(i, j));
}
}
}
return list;
}
2楼，在list在定义时需指定存放类型Top

11 楼pastom（）回复于 2006-12-02 17:13:25 得分 0

用有向图解决Top

12 楼jk88811（你的就是我的，我的还是我的~!）回复于 2006-12-02 17:19:48 得分 0

看来我的算法知识太差了..

得好好修炼一下了!Top

13 楼flyineagle（纸上得来终觉浅，绝知此事要躬行）回复于 2006-12-02 18:23:31 得分 0

diamondwjk(志摩)
1.5才要求指定存放类型的啊，但是不强求啊，1.6才会报错。1.4就没这个啊，所以，这个至少是现在，不是必须的！Top

14 楼FarAwayFromHome（）回复于 2006-12-02 19:59:59 得分 0

for(int i=0;i<lenght;i++)
{
for(int j=i+1;j<lenght;j++)
{
list.add(str.substring(i,j));
}
}
2楼兄弟写的这个段核心算法，不觉得有问题吗？用的是个什么类不重要，关键是怎么实现了，如果按这种思路，恐怕串abc就没有子串ac了，呵呵，很明显，在求子串的过程中，这里求出的子串是不全面的，大侠们不要光学Java类，把Ｃ算法给丢了哦，呵呵。Top

15 楼FarAwayFromHome（）回复于 2006-12-02 20:11:37 得分 0

这个算法在严蔚敏编写的数据结构（Ｃ语言版，清华大学出版社）中写过的，但花了好长时间调试，好像有些问题，最终没有调试成功，她是用的递归写的，如果用非递归，当然是一楼说的穷举法了，我想知道的是穷举法的实现过程，大侠好好想想，两个for循环能了事吗？呵呵。Top

16 楼FarAwayFromHome（）回复于 2006-12-02 20:14:32 得分 0

很多人在ArrayList类上下功夫，没有必要，用Ｃ写出来更好，我能看懂的，别担心，呵呵。不要把什么都交给Ｊava里面的固有类了，呵呵。Top

17 楼malligator（十步之内没有我的爱人）回复于 2006-12-02 20:45:08 得分 0

"abab"?Top

18 楼intotheland（）回复于 2006-12-02 22:20:28 得分 0

我觉得这个问题和以下的问题类似，那位大侠看看，应该有个公式的，不过我忘记了！
有A个球，随机选B个球（0<B<A)出来排列，有多少种不同的排列方法？
比如说吧，有1～33个数字，选其中6个从小到大排列，有多少种排列方法?
Top

19 楼FarAwayFromHome（）回复于 2006-12-02 23:33:19 得分 0

对，差不多，这个问题，你也没有解决？
不过，多少种排法倒是不难，用数学公式算嘛，关键是把排的结果打印出来倒是有点难度了，呵呵，有志于程序研究的，可以参加程序讨论群：32998944,共同探讨。Top

20 楼AWUSOFT（程序设计,一个字:爽!）回复于 2006-12-02 23:40:06 得分 0

哎呀...丢脸了......真是没脸见人了.没有经过深入思考Top

21 楼phuwan（）回复于 2006-12-03 01:40:30 得分 0

学习了～～Top

22 楼ipec（xldelg）回复于 2006-12-03 10:04:42 得分 0

我用一个栈解决了，不过有问题，字符串的长度不能超过12个字符，否则会内存溢出。不明白为什么java程序总会报OutOfMemory异常Top

23 楼bingren03（）回复于 2006-12-03 12:34:47 得分 0

在‘abc’的主串中就没有子串‘ac’，所以上面的几位用java做出求子串是正确的。两个for循环加上一个subSting完全可以把他的子串都列举出来。Top

24 楼AWUSOFT（程序设计,一个字:爽!）回复于 2006-12-03 16:52:18 得分 0

晕。。。就是了。。。我。。。唉。。。Top

25 楼malligator（十步之内没有我的爱人）回复于 2006-12-03 17:39:03 得分 0

FarAwayFromHome真是位高手啊!

PFPF!

我是混不下去了,赶紧闪吧~~Top

26 楼FarAwayFromHome（）回复于 2006-12-03 18:03:57 得分 0

呵呵，bingren03说的很有道理，abc的子串的确没有ac，是我表达不够准确，不过，我的例子是准确的，应该说我是想求出串abc的子集，而不是子串，一个字打错了，呵呵，见谅，既然是子集，那么用两个for循环和subString()方法是不行的，望三思。Top

27 楼AWUSOFT（程序设计,一个字:爽!）回复于 2006-12-03 18:06:58 得分 0

"abcdefghijklmn" 还要得到"agn"这样的子集...我也准备闪人.有空再思考.Top

28 楼AWUSOFT（程序设计,一个字:爽!）回复于 2006-12-03 18:07:44 得分 0

还要得到"aghm".....Top

29 楼malligator（十步之内没有我的爱人）回复于 2006-12-03 18:39:17 得分 0

看到LZ的英明神武,忍不住又要回一下

满足下LZ的BT愿望:C递归版本
-------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 20
int used[N];

void output(char *str);
int diver(char *str, int len, int index);

int main( void )
{
char input[20];
int len;

printf("Please enter a string:");
while(fgets(input, N, stdin) == NULL || input[0] == '\n')
{
printf("Input error!\n");
printf("Please enter a string again:");

}
input[strlen(input) - 1] = '\0';
len = strlen(input);
diver(input, len,0);

return 0;
}

int diver(char *str, int len, int index)
{
if(index >= len)
output(str);
else
{
used[index] = 1;
diver(str, len, index + 1);
used[index] = 0;
diver(str, len, index + 1);

}

return 0;
}

void output(char *str)
{
int i;

printf("{");
for(i = 0;i < N; i++)
if(used[i])
printf("%c",str[i]);
printf("}");
printf("\n");
}
Top

30 楼malligator（十步之内没有我的爱人）回复于 2006-12-03 18:50:47 得分 10

解决方案:
A、组合算法：分别从串中抽取1，2，...，串长N的所有组合！
B、二叉树构造法，想到两种：
1）就是如上C的方法，用一个数组标志记录是否选中每一个字符（每一位都有选中与不选的情况）
2）就是老老实实地构造一棵高度为串长加一的满二叉树（每一层n是串中第n个字符的选和不选作为左右孩子）；然后遍历这棵二叉树。

还要解决一个问题：
上面只考虑所有字符不重复的情况，若有重复的情况（如“aaa”只有一个“a”而不是三个），需要用到一个类似于哈希表之类的容器将重复的子集去掉！

回答完毕！Top

31 楼malligator（十步之内没有我的爱人）回复于 2006-12-03 18:56:25 得分 0

关于组合,受人启发,以前也写了个,也是C的
------------
以下见:
http://community.csdn.net/Expert/topic/5143/5143758.xml?temp=.1741907
-----------
算法:
a[n]={1,1,1,...,0,0}; //初始化:r个1, n-r个0
while(judge(a,n)) //判断是否打印完
{
for i=0 to n-1
if(a[i]==1) print i+1;
println;

for i=0 to n-2
if(a[i]==1 and a[i+1]==0) {a[i]=0;a[i+1]=1; break;}
}
for i=0 to n-1
if(a[i]==1) print i+1;
println;

//定义judge

for i=0 to n-1
if(a[i]==1) return 1;
return 0;

======代码=========
#include <stdio.h>

int judge(int a[],int n)
{
for(int i=n-1;i>0;i--)
if(a[i]==0&&a[i-1]==1) return 1; //存在紧靠着的[10]

return 0;
}

void co( )
{
int a[5] ;
int counter=0,n=5,r=3;

for(int i=0;i<r;i++) //初始化:r个1
a[i]=1;
for(int i=r;i<n;i++) //初始化:n-r个0
a[i]=0;

while(1==judge(a,n)) //判断是否打印完
{
printf("%d : ",++counter); //打印一组结果
for(int i=0;i<n;i++)
if(a[i]==1) printf("%d",i+1);
printf("\n");

for(int i=n-1;i>0;i--)
if(a[i]==0&&a[i-1]==1) //将存在紧靠着的第一个[10]对换位置
{
a[i]=1;
a[i-1]=0;
for(int j=i+1;j<n-j+i;j++)
{
if(a[j]==0&&a[n-j+i]==1)
{
a[j]=1;
a[n-j+i]=0;
}
}
break;
}
}

printf("%d : ",++counter); //打印最后一组结果
for(int i=0;i<n;i++)
if(a[i]==1) printf("%d",i+1);
printf("\n");

printf("\nThe total is :%d\n",counter);//结果总个数

}

int main()
{
co();

return 0;
}

Top

32 楼darksideofjava（秦王骑虎）回复于 2006-12-03 20:23:15 得分 0

简直晕死了。要打印出子集，用下面的代码就可以了。不失一般性，假定字符串中无重复字符，否则将串中每个字符扔入某个Set, 重复自然消除。又假定这个串的长度不大于64。

class SubSet {

public static void main(String[] args) {

String s = args[0];
long count = (1 << s.length());

for (long i = 0;i < count; i++) {
System.out.print('"');
for (int j = 0; j < s.length(); j++) {
if ((i & (1 <<j)) != 0) {
System.out.print(s.charAt(j));
}
}
System.out.println('"');
}
}
}Top

33 楼AWUSOFT（程序设计,一个字:爽!）回复于 2006-12-03 20:40:46 得分 10

哈哈...我也来了,去买饭的时候突然想到求子集的办法:先求1位的子集的下标数组,然后求2位的子集下标数组然后求3位的子集下标数组
package com;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
public class B {
int strlength;//字符串长度
int length;//要求子集长度
int now=0;//子集的位数,表示为求到第几位了
int array[];//保存一个字集的下标
ArrayList list=new ArrayList();//求长度为N的子集会有很多个,第一个都用一个数组表示下标
public B(int strlength,int length)
{
this.strlength=strlength;
this.length=length;
array=new int[length];
now=length;
digui(0);
}

public ArrayList f()
{
return list;
}
public void digui(int start)
{
for(int nI=start;nI<strlength;nI++)
{
array[length-now]=nI;
if(now ==1)//求到最后一位就要产生一个子集下标了,需要复制此时的状态
{
int temp[]=new int[length];
for(int x=0;x<array.length;x++)
{
temp[x]=array[x];
}
list.add(temp);//加一个子集的下标组
}
else
{//如果求的不是最后一位,继续调用,直到是最后一位为止
now--;
digui(nI+1);
}
}
now++;//最后一位求守后返回上一位
}
public static void main(String []args)
{
HashSet strlist=new HashSet();
String str="abc";
//分另求子集长度为:1,2,3..N的下标数组
for(int nI=1;nI<=str.length();nI++)
{
B b=new B(str.length(),nI);
ArrayList list = b.f();//得到长度为N的子集的所有可能下标数组
Iterator it = list.iterator();
while(it.hasNext())
{
int c[]=(int[])it.next();
String substr="";
for(int j=0;j<c.length;j++)
{
substr+=str.charAt(c[j]);
}
strlist.add(substr);//产生子集
}
}
Iterator ir = strlist.iterator();
while(ir.hasNext())
{
System.out.println(ir.next());
}
}
}
Top

34 楼kaiy_ai（）回复于 2006-12-04 10:01:12 得分 0

学习~~Top

35 楼Apollo125（）回复于 2006-12-04 11:49:45 得分 0

darksideofjava(秦王骑虎)

能不解释下long count = (1 << s.length()); 什么意思
起到什么作用啊

学习Top

36 楼assassin5616（）回复于 2006-12-04 13:19:42 得分 0

一定要用递归吗？不用行不行.
还有AWUSOFT。能不能解释一下你的digui这个函数的这一行
for(int nI=start;nI<strlength;nI++)。
我没怎么看明白，感觉不应该循环这么多次应该当NI增加到strlength - length就可以了吧?不知道是不是，解释一下
Top

37 楼AWUSOFT（程序设计,一个字:爽!）回复于 2006-12-04 13:37:12 得分 0

比如现在是abcde
但是我要求的是2位的子集
那么我求的结果应该是这些数组:01,02,03,04,12,13,14,23,24,34吧
首先进去的时候:now,lenght=2;strlenght=5;
开始调用digui(0);
进入for,这时候nI=0;
array[lenght-now]=nI----->a[0]=0找到一个第一位的
判断now不是1

now--; -------------->now变为1;
进入另一个递归B(digui(nI+1))
进入它的for,这时候nI=1开始
array[lenght-now]=nI---->a[1]=1
判断now=1--->复制此时的数组值为01
进入下一次循环这时候nI=2
array[lenght-now]=nI---->a[1]=2
判断now=1--->复制此时的数组值为02
...
最后nI==strlenght,总共产生了,01,02,03--0strlenght-1;这些数组
退出循环
now++;------------>这时候now=2;

返回上一个递归--->也就是第一个递归中的else{now--;digui(nI+1)}这里执行完毕
第一个递归nI++;-------------->nI变为1
array[lenght-now]=nI----->a[0]=1找到第二个第一位的
此时再判断now!=1
再进去找(now--;digui(nI+1))--->digui(2)
这一次就是找到了12,13...1strlenght-1

只能这样解释了...如果有10位8位,那么这个递归的深度太深了无法解释

Top

38 楼assassin5616（）回复于 2006-12-04 14:04:59 得分 0

39 楼assassin5616（）回复于 2006-12-04 14:07:45 得分 0

晕倒，回复错了，谢谢AWUSOFT的回答，还有一个地方不明白，以你举的例子来说。
比如现在是abcde
但是我要求的是2位的子集
那么我求的结果应该是这些数组:01,02,03,04,12,13,14,23,24,34吧
根据这一句
for(int nI=start;nI<strlength;nI++)。
当nI = 0, 1, 2, 3的时候你就可以求出01,02,03,04,12,13,14,23,24,34这些组合了，可是这个时候循环还没有结束，nI会继续增加到4,这个时候该怎么办呢Top

40 楼darksideofjava（秦王骑虎）回复于 2006-12-04 15:19:58 得分 0

To : Apollo125

long count = (1 << s.length()) 用来计算子集的个数，是2的s.length()次方. 例如abcd的子集就有16个。因此外层循环每执行一次，就输出一个子集。在内层循环中，循环变量的位模式对应一个子集, 如果某位为0，不打印，为1则打印。

子集数目非常巨大，对于64个字符的串，我粗略估算一下，如果每秒打印1百万个子集，需要打印57万年！Top

41 楼AWUSOFT（程序设计,一个字:爽!）回复于 2006-12-04 15:25:51 得分 0

To:assassin5616()
nI到4了又怎么样了?进去的时候nI等五,里的for循都不执行的啊...
digui(5)这进去到进里,没有循环,直接now++;又退出来了Top

42 楼zwgs1985（流氓狗）回复于 2006-12-04 17:39:13 得分 0

package easy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.List;
/**
* 按照二进制数的排列方法打印子集
* @author Administrator
*
*/
public class PaiLieZuHe {

private static List Pop(String s) throws IOException {
// s = br.readLine();
int m = s.length();
int n = 1;
//汗，忘了怎么计算幂了~~~
for (int k = 0; k < m; k++) {
n *= 2;
}
String s1 = s;
for (int i = 0; i < n; i++) {
s1 = Integer.toBinaryString(i);
if (s1.length() < m) {
//补齐位数，和S长度一样
for (int x = 0; x <= m - s1.length(); x++) {
s1 = "0" + s1;
}
}
char[] a = s1.toCharArray();
//如果二进制位上的数字是1 ，则打印字符串S相对应的字符
for (int j = 0; j < m; j++) {
if (a[j] == '1') {
System.out.print(s.substring(j, j + 1));
} else {
System.out.print("");
}
}
System.out.println();
}
return null;
}

/**
* @param args
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Please input a string: ");
Pop(br.readLine());
}

}
=====================
晕死了,测试了一下,有N多BUG~~~Top

43 楼zwgs1985（流氓狗）回复于 2006-12-04 17:48:41 得分 0

package easy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.List;

/**
* 按照二进制数的排列方法打印子集
*
* @author Administrator
*
*/
public class PaiLieZuHe {

private static List Pop(String s) throws IOException {
// s = br.readLine();
int m = s.length();
int n = 1;
// 汗，忘了怎么计算幂了~~~
for (int k = 0; k < m; k++) {
n *= 2;
}
String s1 = s;
for (int i = 0; i < n; i++) {
s1 = Integer.toBinaryString(i);
if (s1.length() < m) {
int y = s1.length();
// 补齐位数，和S长度一样
for (int x = 0; x < (m-y); x++) {
s1 = "0" + s1;
}
}
char[] a = s1.toCharArray();
// 如果二进制位上的数字是1 ，则打印字符串S相对应的字符
for (int j = 0; j < m; j++) {
if (a[j] == '1') {
System.out.print(s.substring(j, j + 1));
} else {
System.out.print("");
}
}
System.out.println();
}
return null;
}

/**
* @param args
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Please input a string: ");
Pop(br.readLine());
}

}
=================================
OK,终于好了,可是效率太低了,呵呵,不多想了~~~~~Top

44 楼assassin5616（）回复于 2006-12-04 19:18:15 得分 0

给个C++的，非递归的，简化处理一下，打印{0,1,2,...n-1}中任意数的组合方案，如果大家要打印任意数，把0,1,2..n-1考虑作下标就好了。
void printC(const vector<int> vec, int n)
{
for(int i = 0; i < n; i++)
{
cout<<vec[i];
}
cout<<endl;
}
//这个函数负责打印，n代表总数，num代表选择几个，比如n=5,num=3代表五个数里任选三个
void printCombination(int n, int num)
{
vector<int> vec(n);
for (int i = 0; i < vec.size(); i++)
{
vec[i] = i;
}
int t = num;
vector<int> c(t + 2);
for (int j = 0; j < t; j++)
{
c[j] = j;
}
c[t] = vec.size();
c[t + 1] = 0;

while (1)
{
printC(c, t);
int j = 0;
while( (c[j] + 1) == c[j + 1])
{
c[j] = j;
j++;
}
if (j >= t)
{
break;
}
c[j]++;

}
}Top

45 楼kim_ouyang（）回复于 2006-12-09 13:27:23 得分 0

/*用两个循环就可以实现了.我们从字符串的最后一个字符开始取,每次取一个,把后一次取的字符与前面所解析出的字符或字符串再组合就可以了.
比如:abc
第一次取最后一个字符c,存在一种情况c
第二次取c前面的一个字符b,存在情况b,然后再把b与前一次的所有情况组合,即存在bc
第三次取a,然后再把a与前两次的情况组合,即存在a,ac,ab,abc四种情况,
最后结果为c,b,bc,a,ac,ab,abc七种情况.
这种算法的效率还挺高的.
参考代码如下:*/
import java.util.*;
import java.io.*;
public class Test{

public static void main(String[] args)throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("请输入你要测试的字符串:");
String readStr=br.readLine().trim();
System.out.println("---------------------");
if(readStr.length()>0){
Object[] arr=Test.toSubString(readStr);
for(int i=0;i<arr.length;i++){
System.out.println((String)arr[i]);
}
System.out.println("一共有"+arr.length+"情况");
}else{
System.out.println("测试字符串不能为空!" );
System.exit(0);
}
}
public static Object[] toSubString(String str) {
ArrayList list = new ArrayList();//保存解析的字符
HashSet set=new HashSet();//用HashSet去掉重复字符
if (str != null) {
int len=str.length();
for(int i=len-1;i>=0;i--){
String s=String.valueOf(str.charAt(i)).trim();
if(s.length()==0) continue;//跳过空字符
list.add(s);
set.add(s);
int size=list.size();
for(int j=0;j<size-1;j++){
String re=s+(String)list.get(j);
list.add(re);
set.add(re);
}
}
}
Object[] arr=set.toArray();
Arrays.sort(arr);//排序
return arr;
}
}
Top

46 楼xblue3（http://my.6cncn.cn）回复于 2006-12-09 14:34:10 得分 0

西安软件园java-群
34096076
欢迎加入西安软件园java群,主要讨论J2EE+J2ME,提供相互交流和帮助的空间

建议使用"部门+姓名"命名呢称
Top

47 楼fafa2006cici（）回复于 2006-12-09 22:05:27 得分 0

交流Top

48 楼JonsenElizee（）回复于 2006-12-10 00:35:44 得分 0

To: darksideofjava(秦王骑虎)
Wonderful! this is the admiring code.
Copy from darksideofjava:
-------------------------------------------------------------------------------------
public class TestSubstring2
{
public static void main(String[] args)
{
String string = "abcd";
long count = (1 << string.length());
for (long i = 0; i < count; i++)
{
System.out.print("'");
for (int j = 0; j < string.length(); j++)
{
if ((i & (1 << j)) != 0)
{
System.out.print(string.charAt(j));
}
}
System.out.print("' ");
}
}
}
-------------------------------------------------------------------------------------
Top

49 楼JonsenElizee（）回复于 2006-12-10 00:38:29 得分 0

This is the four-letter one by me:

-------------------------------------------------------------------------------------
import java.util.*;

public class TestSubstring
{
public static ArrayList convertIntoArrayList(String string)
{
ArrayList arrayList = new ArrayList();
for (int i = 0; i < string.length(); i++)
{
arrayList.add(string.substring(i, i + 1));
}
return arrayList;
}

public static ArrayList getSet(ArrayList arrayList)
{
if (arrayList.size() == 1)
{
return arrayList;
}
else
{
String item0 = (String)arrayList.get(0);
//get the sub set of the sub array list
arrayList.remove(0);
ArrayList subSet = TestSubstring.getSet(arrayList);
ArrayList set = new ArrayList();
set.add(item0);
for (int i = 0; i < subSet.size(); i++)
{
set.add(subSet.get(i));
set.add(item0 + subSet.get(i));
}

return set;
}
}

public static void main(String[] arg)
{
while (true)
{
String string = javax.swing.JOptionPane.showInputDialog(null, "Input a string please (string.length < 16)");
if (string == null)
{
System.exit(0);
}
if (string.trim().length() == 0)
{
continue;
}
ArrayList arrayList = TestSubstring.getSet(TestSubstring.convertIntoArrayList(string));
System.out.print("' ' ");
for (int i = 0; i < arrayList.size(); i++)
{
System.out.print("'" + arrayList.get(i) + "' ");
}
System.out.println();
}
}
}
-------------------------------------------------------------------------------------
Top

50 楼areswang（西游不记）回复于 2006-12-10 12:37:04 得分 0

mark!
Top

51 楼FarAwayFromHome（）回复于 2006-12-12 12:58:36 得分 0

谢谢各位的支持，待我把各个程序看一遍，执行无误后再给分！
Top

52 楼AWUSOFT（程序设计,一个字:爽!）回复于 2006-12-12 13:16:04 得分 0

哇。。。就这20分，讨论还真多哩。。Top

53 楼kim_ouyang（）回复于 2006-12-12 23:05:47 得分 0

public class TestSubstring2
{
public static void main(String[] args)
{
String string = "abcd";
long count = (1 << string.length());
for (long i = 0; i < count; i++)
{
System.out.print("'");
for (int j = 0; j < string.length(); j++)
{
if ((i & (1 << j)) != 0)
{
System.out.print(string.charAt(j));
}
}
System.out.print("' ");
}
}
}
不严谨,假如测试字符串为abcc呢,是不是有几个重复的子串呢?Top

54 楼Tinasoft（）回复于 2006-12-13 00:06:11 得分 0

在《数据结构与算法》这本书中有这样的类子，很受益。Top