谁能写出这个程序？

Question

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

Answer 1

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;
}

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

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在定义时需指定存放类型

Answer 9

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

Answer 10

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类，把Ｃ算法给丢了哦，呵呵。

Answer 11

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

Answer 12

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

Answer 13

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

Answer 14

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

Answer 15

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

Answer 16

FarAwayFromHome真是位高手啊!PFPF!我是混不下去了,赶紧闪吧~~

Answer 17

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

Answer 18

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

Answer 19

看到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");   
  }   

Answer 20

解决方案:
A、组合算法：分别从串中抽取1，2，...，串长N的所有组合！
B、二叉树构造法，想到两种：
    1）就是如上C的方法，用一个数组标志记录是否选中每一个字符（每一位都有选中与不选的情况）
    2）就是老老实实地构造一棵高度为串长加一的满二叉树（每一层n是串中第n个字符的选和不选作为左右孩子）；然后遍历这棵二叉树。还要解决一个问题：
上面只考虑所有字符不重复的情况，若有重复的情况（如“aaa”只有一个“a”而不是三个），需要用到一个类似于哈希表之类的容器将重复的子集去掉！回答完毕！

Answer 21

关于组合,受人启发,以前也写了个,也是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;//定义judgefor 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;
}

Answer 22

简直晕死了。要打印出子集，用下面的代码就可以了。不失一般性，假定字符串中无重复字符，否则将串中每个字符扔入某个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('"');
}
}
}

Answer 23

哈哈...我也来了,去买饭的时候突然想到求子集的办法:先求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());
}
}
}

Answer 24

darksideofjava(秦王骑虎)能不解释下long count = (1 << s.length()); 什么意思
起到什么作用啊学习

Answer 25

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

Answer 26

比如现在是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不是1now--;      -------------->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位,那么这个递归的深度太深了无法解释
             
              

Answer 27

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

Answer 28

晕倒，回复错了，谢谢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,这个时候该怎么办呢

Answer 29

To : Apollo125long count = (1 << s.length()) 用来计算子集的个数，是2的s.length()次方. 例如abcd的子集就有16个。 因此外层循环每执行一次，就输出一个子集。在内层循环中，循环变量的位模式对应一个子集, 如果某位为0，不打印，为1则打印。子集数目非常巨大，对于64个字符的串，我粗略估算一下， 如果每秒打印1百万个子集，需要打印57万年！

Answer 30

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

Answer 31

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~~~

Answer 32

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,终于好了,可是效率太低了,呵呵,不多想了~~~~~

Answer 33

给个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]++; }
}

Answer 34

/*用两个循环就可以实现了.我们从字符串的最后一个字符开始取,每次取一个,把后一次取的字符与前面所解析出的字符或字符串再组合就可以了.
比如: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;
    }
}

Answer 35

西安软件园java-群
34096076
欢迎加入西安软件园java群,主要讨论J2EE+J2ME,提供相互交流和帮助的空间建议使用"部门+姓名"命名呢称

Answer 36

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("' ");
        }
    }
}
-------------------------------------------------------------------------------------

Answer 37

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();
        }
    }
}
-------------------------------------------------------------------------------------

Answer 38

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呢,是不是有几个重复的子串呢?