查找首个重复字符串算法

/**
?* 例“abncdbmn”,首个重复字母为b
?*/
package cn.edu.moon.alg;

import java.util.BitSet;
import java.util.HashMap;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
?* @author Administrator
?*
?*/
public class FindSameChar { ?
?? ? ?
??? public? char findSameChar(String str){?? ?
??????? int length = str.length();?? ?
??????? for(int i = 0;i<length;i++)?? ?
??????????? for(int j=i+1;j<length;j++)?? ?
??????????? {?? ?
??????????????? if(str.charAt(i)==str.charAt(j)){?? ?
??????????????????? return str.charAt(i);?? ?
??????????????? }?? ?
??????????? } ?
??????? return 0; ?
??? }?? ?
?????? ?
??? public? char findSameMap(String str){?? ?
??????? HashMap<Character, Integer> map = new HashMap<Character, Integer>();?? ?
??????? for(int i=0;i<str.length();i++){?? ?
??????????? if(map.containsKey(str.charAt(i))){ ?
??????????????? return str.charAt(i); ?
??????????? }else?? ?
??????????? {?? ?
??????????????? map.put(Character.valueOf(str.charAt(i)), Integer.valueOf(1));?? ?
??????????? }?? ?
??????? } ?
??????? return 0; ?
??? } ?
???? ?
??? public? char findSameBitSet(String str) { ?
??????? BitSet set = new BitSet(255); ?
??????? for (int i = 0; i < str.length(); i++) { ?
??????????? if (set.get(str.charAt(i))) { ?
??????????????? return str.charAt(i); ?
??????????? } else { ?
??????????????? set.set(str.charAt(i), true); ?
??????????? } ?
??????? } ?
??????? return 0; ?
??? } ?
???? ?
??? private static final Pattern p = Pattern.compile("(\\w).*\\1");?? ?
???? ?
??? public? String findSameRegEx(String s) {?? ?
??????? Matcher m = p.matcher(s);?? ?
??????? if (m.find()) {?? ?
??????????? return m.group(1);?? ?
??????? } else {?? ?
??????????? return null;?? ?
??????? }?? ?
??? }? ?
???? ?
??? private static final long TIMES = 100*1000*1000; ?
???? ?
??? public static void main(String[] args) { ?
??????? char result = 0; ?
??????? FindSameChar test = new FindSameChar();
??????? long t = System.currentTimeMillis(); ?
??????? for (long i = 0; i < TIMES; i++) { ?
??????????? result = test.findSameChar("abcdefghijklmnopqrstbab"); ?
??????? } ?
??????? t = System.currentTimeMillis() - t; ?
??????? System.out.println("findSameChar : Result " + result + " in " + t); ?
???????? ?
??????? result = 0; ?
??????? t = System.currentTimeMillis(); ?
??????? for (long i = 0; i < TIMES; i++) { ?
??????????? result = test.findSameMap("abcdefghijklmnopqrstbab"); ?
??????? } ?
??????? t = System.currentTimeMillis() - t; ?
??????? System.out.println("findSameMap : Result " + result + " in " + t); ?
?
??????? result = 0; ?
??????? t = System.currentTimeMillis(); ?
??????? for (long i = 0; i < TIMES; i++) { ?
??????????? result = test.findSameBitSet("abcdefghijklmnopqrstbab"); ?
??????? } ?
??????? t = System.currentTimeMillis() - t; ?
??????? System.out.println("findSameBitSet : Result " + result + " in " + t); ?
???????? ?
??????? String strResult = null; ?
??????? t = System.currentTimeMillis(); ?
??????? for (long i = 0; i < TIMES; i++) { ?
??????????? strResult = test.findSameRegEx("abcdefghijklmnopqrstbab"); ?
??????? } ?
??????? t = System.currentTimeMillis() - t; ?
??????? System.out.println("findSameRegEx : Result " + strResult + " in " + t); ?
??? } ?
}? ?
/**
?* 运行结果，原以为findSameMap最快，哈哈，最终最简单的总是最快的
?? ?findSameChar : Result a in 10547
?? ?findSameMap : Result b in 246000
?? ?findSameBitSet : Result b in 76328
?? ?findSameRegEx : Result a in 127187
*/