求效率高的算法！！

Question

第二个问题：将两个字符串比较，取出里面最大的子串。
     如："abcdefg"和"aebcdeg"最大的字串为"bcde"
实现代码：
/*
 * Created on 2004-4-9
 *
 * To change the template for this generated file go to
 * Window - Preferences - Java - Code Generation - Code and Comments
 */
/**
 * @author Ai92
 *
 * To change the template for this generated type comment go to
 * Window - Preferences - Java - Code Generation - Code and Comments
 */
//import java.math.*;
public class thesame {
public static void main(String[] args)
{
int maxlength=0;
String a="ilove java,ilove myselftoo";
String b="ilove myselftoo,ilove jaa";
String thisa=null;
for(int i=0;i<a.length();i++)
{
int beginn=i;
for(int j=0;j<b.length();j++)
{
int count=0;
while(i<a.length()&&j<b.length()&&a.charAt(i)==b.charAt(j))
{
++i;
++j;
++count;
}
if(count>maxlength)
{
maxlength=count;
thisa=a.substring(beginn+1,i);
}
}
}
System.out.println("最长的个数为："+maxlength);
System.out.println("字符串为："+thisa);

}
}

Answer 1

第一个问题:思路就是判断当前的字符是不是第一次出现
import java.io.*;
public class Jiaogu
{
private String gets=null;//定义字符串接受将要处理的字符串
public static void main(String[] args)throws Exception
{
Jiaogu jg=new Jiaogu();
jg.getString();
jg.qurongyu();
}
private void qurongyu()//冗余处理函数
{
System.out.println("去冗余输出为：");
System.out.print(gets.charAt(0));
for(int i=1;i<gets.length();i++){

if(gets.indexOf(gets.charAt(i))==i){
System.out.print(gets.charAt(i));
}
}
}

private void getString()throws IOException //从键盘接受字符串
{
System.out.println("请输入要去冗余的字符串：");
BufferedReader bfs=new BufferedReader(new InputStreamReader(System.in));
gets=bfs.readLine();
bfs.close();
}
}

Answer 2

哎呀，wind多谢提醒，我还真忘了有现成的方法可以用了！！
呵呵，谢谢。记得接分。呵呵
还有谁提出更好的方法？
我敬等回信！！

Answer 3

第二个问题:思路跟你的差不多,只不过是利用了indexOf罢了
另，你的那个有点问题，第一个字母丢掉了。
public class thesame {
public static void main(String[] args)
{
int maxlength=0;
String a="ilove java,ilove myselftoo";
String b="ilove myselftoo,ilove jaa";
String thisa=""; boolean flag = false;
int count = 0;
String theStr = "";
for(int i=0;i<b.length();i++){
if(flag){
thisa += b.charAt(i);
}else{
thisa = String.valueOf(b.charAt(i));
}

if(a.indexOf(thisa)>=0){
flag = true;
count++;

if(count>maxlength){
maxlength = count;
theStr = thisa;
}
}else{
flag = false;
count = 0;
thisa = "";
}
}

System.out.println("最长的个数为："+maxlength);
System.out.println("字符串为："+theStr);

}
}

Answer 4

第一题，判断是不是第一个，不应该判断原字符串，如果原字符串很长，就非常影响效率。
每次 print ，也是影响效率的。
StringBuffer 对于添加删除字符串操作，效率比较高。public static void test(String s) {
StringBuffer str=new StringBuffer();
for(int i=0;i<s.length();i++) {
char c=s.charAt(i);
if(str.indexOf(""+c)<0) {
str.append(c);
}
}
System.out.println(str);
}

Answer 5

第二题，因为最大长度的串可能为多个，所以返回一个 List
public static List test2(String str1, String str2) {
List l = new ArrayList();
String s1 = str1, s2 = str2;
int n;
boolean flag = true;
if (str1.length() > str2.length()) { // 将短串赋给 s1
s1 = str2;
s2 = str1;
}
n = s1.length();
for (int i = n; i > 0 && flag; i--) {
for (int j = 0; j <= n - i; j++) {
String t = s1.substring(j, j + i); // 从长到短取短串的子串
if (s2.indexOf(t) >= 0) { // 判断是否为长串的子串，如果是，标记上，就不继续减小子串的长度了，只对比完这一长度的所有串
flag = false;
l.add(t);
}
}
}
return l;
}

Answer 6

是不是于哥,java搞得怎么样了

Answer 7

第一个问题：无论怎么说，数组的效率应该是最高的，如果不考虑局限性，我觉得下面方法效率最高private void qurongyu(){
char[] result=new char[256];
int index=0;
char temp;
out:
for(int i=0;i<gets.length();i++){
temp=gets.charAt(i);
for(int j=0;j<index;j++){
if(result[j]==temp)
continue out;
}
result[index++]=temp;
}
System.out.println(new String(result,0,index));
}

Answer 8

support topglory:
我刚才看了一下 String 的 indexOf 方法，效率不高，判断了好多东西，还是自己写的比较快一些。

Answer 9

“归并排序的机制”
就是 topglory(大叔) 的做法。

Answer 10

第一个问题：
如果字符串都是ASCII码的话，判断是否第一次出现可用数组表示：
char[] src = str.toCharArray();
char[] chars = new char[26];int index ;
for(int i =0;i<src.length;i++){
    index = Character.toLowerCase(String.src[i])-'a';
    if(chars[index]==0){
        //todo: 输出
        chars[index]=1;
    }
}

Answer 11

第二个问题可以对“改进的KMP模式匹配算法”修改一下（记住最长的0串的长度和起始位置），然后对原字符串计算即可。这里本身记住0串的长度和起始位置的问题和原问题很类似，但简单得多，因为只需要判断是否为0即可。

Answer 12

public class MyTest {
  String testStr;
  private final int SIZE = 1000000;
  byte[] init = new byte[SIZE];  boolean[] memo = new boolean[128];
  public MyTest() {
  }  public void initStr() {
    java.util.Random random = new java.util.Random();
    for (int i = 0; i < SIZE; i++) {
      int rand = random.nextInt(128);
      init[i] = (byte) rand;
    }
    testStr = new String(init);
  }  public String getResult() {
    StringBuffer strBuf = new StringBuffer("");
    char temp;
    for (int i = 0; i < testStr.length(); i++) {
      temp = testStr.charAt(i);
      if (!memo[temp]) {
        strBuf.append(temp);
        memo[temp] = true;
      }
    }
    return strBuf.toString();
  }  private String qurongyu() { //冗余处理函数
    StringBuffer strBuf = new StringBuffer("");    strBuf.append(testStr.charAt(0));
    for (int i = 1; i < testStr.length(); i++) {
      boolean key = true;
      for (int j = i - 1; j >= 0; j--) {
        if (testStr.charAt(i) == testStr.charAt(j)) {
          key = false;
          break;
        }
      }
      if (!key)
        continue;      if (key) {
        strBuf.append(testStr.charAt(i));
      }
    }
    return strBuf.toString();
  }  public static void main(String[] args) {
    MyTest myTest1 = new MyTest();
    myTest1.initStr();    long btime = System.currentTimeMillis();
    String result = myTest1.getResult();
    long etime = System.currentTimeMillis();
    System.out.println(result);
    System.out.println("Time Used:" + (etime - btime));    btime = System.currentTimeMillis();
    result = myTest1.qurongyu();
    etime = System.currentTimeMillis();
    System.out.println(result);
    System.out.println("Time Used:" + (etime - btime));
  }
}

Answer 13

public class MyTest2 {
  String stra;
  String strb;
  private final int SIZE = 500;
  byte[] init = new byte[SIZE];  public MyTest2() {
  }  public void initStr() {
    java.util.Random random = new java.util.Random();
    for (int i = 0; i < SIZE; i++) {
      int rand = random.nextInt(26);
      init[i] = (byte) (rand + 97);
    }
    stra = new String(init);
    for (int i = 0; i < SIZE; i++) {
      int rand = random.nextInt(26);
      init[i] = (byte) (rand + 97);
    }
    strb = new String(init);
  }  public int finder() {
    int lena = stra.length();
    int lenb = strb.length();    int maxlen = (lena >= lenb ? lenb : lena); //最大长度为2个字符串中短的一个    String suba = null;
    String subb = null;    int cnt = 0;
    while (maxlen > 0) { //找到为止
      for (int i = 0; i < lena - maxlen + 1; i++) {
        suba = stra.substring(i, maxlen + i);
        for (int j = 0; j < lenb - maxlen + 1; j++) {
          cnt++;
          subb = strb.substring(j, maxlen + j);
//          System.out.println("len:" + maxlen + "||" + suba + "||" + subb);
          if (suba.equals(subb)) {
            System.out.println("maxLengh:" + maxlen);
            System.out.println("str=" + suba);
            System.out.println("i=:"+i+" j=:"+j);
            return cnt;
          }
        }
      }
      maxlen--;
    }
    System.out.println("not find! :(");
    return cnt;
  }  public void yourfinder() {
    int maxlength=0;
    String thisa = null;
    for (int i = 0; i < stra.length(); i++) {
      int beginn = i;
      for (int j = 0; j < strb.length(); j++) {
        int count = 0;
        while (i < stra.length() && j < strb.length() && stra.charAt(i) == strb.charAt(j)) {
          ++i;
          ++j;
          ++count;
        }
        if (count > maxlength) {
          maxlength = count;
          thisa = strb.substring(beginn + 1, i);
        }
      }
    }
    System.out.println("最长的个数为：" + maxlength);
    System.out.println("字符串为：" + thisa);
  }  public static void main(String[] args) {
    MyTest2 myTest21 = new MyTest2();
    myTest21.initStr();
    long btime = System.currentTimeMillis();
    int cnt = myTest21.finder();
//    System.out.println((int)'a');
    long etime = System.currentTimeMillis();
    System.out.println(cnt);
    System.out.println("Time Used:" + (etime - btime));    btime = System.currentTimeMillis();
    myTest21.yourfinder();
//    System.out.println((int)'a');
    etime = System.currentTimeMillis();
    System.out.println("Time Used:" + (etime - btime));
    System.out.println(myTest21.stra);
    System.out.println(myTest21.strb);
  }}

Answer 14

问题1 topglory(大叔) 提供的算法应该是效率比较高的（当串的长度比较大时）
问题2 你自己的算法好像有BUG，没有通过我的测试
我提供了一个算法，没有什么技巧，就是硬比。可以改进的地方是不要每次都用substring生成新的串（这样效率太低），而自己做个算法比较起点到终点是否相等（一旦不等就终止本次比较）。

Answer 15

这个版本比上个版本的效率高近8倍！  public int finderVer2() {
    int lena = stra.length();
    int lenb = strb.length();    int maxlen = (lena >= lenb ? lenb : lena); //最大长度为2个字符串中短的一个    int cnt = 0;
    while (maxlen > 0) { //找到为止
      for (int i = 0; i < lena - maxlen + 1; i++) {
        for (int j = 0; j < lenb - maxlen + 1; j++) {
          cnt++;
          boolean cmp=true;
          for (int k=0;k<maxlen;k++){
            if (bytesa[i+k]!=bytesb[j+k]){
              cmp=false;
              break;
            }
          }
          if (cmp) {
            System.out.println("maxLengh:" + maxlen);
            System.out.println("i=:"+i+" j=:"+j);
            return cnt;
          }
        }
      }
      maxlen--;
    }
    System.out.println("not find! :(");
    return cnt;
  }

Answer 16

我写了个比大叔快的算法（第一个）String qurongyu(String str){
char[] temp = new char[256];
StringBuffer result = new StringBuffer(256);
int count = 0;
char c = 0;
for(int i=0;i<str.length();i++){
c = str.charAt(i);
if(temp[c] == 0){
 temp[c] = c;
 result.append(c);
}
}
return  result.toString();
}