2列の回転
1949 ワード
一つの文字列Aに対して、Aの前の任意の部分を後ろにずらして形成された文字列をAの回転語と呼ぶ.例えば、A=「12345」、Aの回転語は「12345」、「23451」、「34512」、「45123」および「51234」である.2つの文字列AとBについて、AとBが互いに回転語であるか否かを判断してください.2つの文字列AとBとその長さlena,lenbを指定し、互いに回転語であるかどうかを表すbool値を返します.
テストサンプル:
"cdab",4,"abcd",4
戻る:true
参考記事:KMPを最初から最後まで徹底的に理解https://www.nowcoder.com/study/vod/1/1/4
参考答案python版
-- coding:utf-8 --
class Rotation:def chkRotation(self, A, lena, B, lenb):
write code here
Java版import java.util.*;
public class Rotation {public boolean chkRotation(String a, int lena, String b, int lenb) {if (a == null || b == null || lena != lenb) {return false;}String b2 = b + b;return getIndexOf(b2, a) != -1;}
}
テストサンプル:
"cdab",4,"abcd",4
戻る:true
参考記事:KMPを最初から最後まで徹底的に理解https://www.nowcoder.com/study/vod/1/1/4
参考答案python版
-- coding:utf-8 --
class Rotation:def chkRotation(self, A, lena, B, lenb):
write code here
if lena != lenb:
return False
else:
combineStr = A + A
print combineStr
if B in combineStr:
return True
else:
return False
Java版import java.util.*;
public class Rotation {public boolean chkRotation(String a, int lena, String b, int lenb) {if (a == null || b == null || lena != lenb) {return false;}String b2 = b + b;return getIndexOf(b2, a) != -1;}
// KMP Algorithm
public int getIndexOf(String s, String m) {
if (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 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;
}
}