一个面试问题

Question

给出一段sequence , 找出重复的sub sequence,并给出重复次数。比如：“aasdhowchfjikaboywefasdhohowcjiovnasdhowc”输出：
dh: 3
ji: 2
sd: 3
as: 3
wc: 2
ow: 3
ho: 4
how: 3
sdh: 3
asd: 3
owc: 2
dho: 3
howc: 2
asdh: 3
dhow: 2
sdho: 3
sdhow: 2
asdho: 3
asdhow: 2

Answer 1

用map做就可以了的。。
大致思路。
public static void main(String[] args) throws Exception {
Map<String, Integer> map = new HashMap<String, Integer>();
String data = "aasdhowchfjikaboywefasdhohowcjiovnasdhowc";
// 看楼主的意思是2个以上？我还是从一个开始算。
for (int i = 1; i < data.length(); i++) {
for (int j = 0; j < data.length() - i; j++) {
String temp = data.substring(j, j + i);
System.out.println(temp);
if (map.containsKey(temp)) {
Integer in = map.get(temp);
map.put(temp, in + 1);
} else {
map.put(temp, 1);
}
}
}
Map<String, Integer> cloneMap = new HashMap<String, Integer>();
cloneMap.putAll(map);
for(Iterator<String> it = cloneMap.keySet().iterator();it.hasNext();){
if(cloneMap.get(it.next()) == 1){
it.remove();
}
}
System.out.println(cloneMap);
}

Answer 2

import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.HashSet;
class Test{
    public static void main(String[] args){
String s="aasdhowchfjikaboywefasdhohowcjiovnasdhowc",sub="";
Matcher m;
int count=0;
HashSet<String> set=new HashSet<String>();
for(int b=0;b<s.length();b++){
for(int e=b+2;e<s.length();e++){
if (!set.contains(sub=s.substring(b,e))){
m=Pattern.compile(sub).matcher(s);
while(m.find())
count++;
if (count>1){
System.out.println(sub+" "+count);
set.add(sub);
}
if (count>0)
count=0;
else
break;
}
}
}
}
}