KMPアルゴリズムを用いて1つのツリーが別のツリーのサブツリーであるか否かを判断する
1014 ワード
方法:KMPアルゴリズムを利用して、2つの木を序列化して、それぞれ1回の木を遍歴して、2つの文字列を得て、時間の複雑度はO(n)です
KMP問題:String 1,String 2,String 2がString 1のサブストリングである場合、String 2のString 1での開始位置を返します.
KMP問題:String 1,String 2,String 2がString 1のサブストリングである場合、String 2のString 1での開始位置を返します.
public static int getIndexOf(String s, String m){
if(s == null || m == null || m.length() < 1 || s.length() < m.length()){
return -1;
}
char[] ss = s.toCharArray();
char[] ms = m.toCharArray();
int si = 0;
int mi = 0;
int[] next = getNextArray(ms);
while(si < ss.length && mi < ms.length){
if(ss[si] == ms[mi]){
si++;
mi++;
}else if(next[mi] == -1){
si++;
}else{
mi = next[mi];
}
}
return mi == ms.length ? si - mi : -1;
}
public static int[] getNextArray(char[] ms){
if(ms.length == 1){
return new int[] {-1};
}
int[] next = new int[ms.length];
next[0] = -1;
next[1] = 0;
int pos = 2;
int cn = 0;
while(pos < next.length){
if(ms[pos - 1] == ms[cn]){
next[pos++] = ++cn;
}else if (cn > 0){
cn = next[cn];
}else{
next[pos++] = 0;
}
}
return next;
}