인터뷰 질문:한 문자열이 다른 문자열의 회전인지 확인합니다.
오늘 소프트웨어 개발자 자리에 대한 면접에서 제 친구가 다음과 같은 질문을 받았습니다.
의 스트링 2가 됩니다.s1 ★★★★★★★★★★★★★★★★★」s2하시겠습니까?s1의 회전 버전입니다.s2
예:
ifs1 = "stackoverflow"하다
"tackoverflows"
"ackoverflowst"
"overflowstack"
서 「」라고 합니다."stackoverflwo"는 회전 버전이 아닙니다.
을 사용하다
s2긴 를.s1회전 포인트가 됩니다..s2그 시점에서 얻으려고s2a★★★★★★★★★★★★★★★★★」s2b만약을 됩니다.concatenate(s2a,s2b) == s1
그것은 나와 내 친구에게 좋은 해결책으로 보인다.하지만 면접관은 다르게 생각했다.그는 좀 더 간단한 해결책을 요구했다. 좋을지 주세요.Java/C/C++
잘 부탁드립니다.
★★★★★★★★★★★★★★★★★★.s1 ★★★★★★★★★★★★★★★★★」s2이가같같 같같같다다 다음, "이러면 안 돼요?"를 합니다.s2의 서브스트링입니다.s1되어 있습니다.s1:
algorithm checkRotation(string s1, string s2)
if( len(s1) != len(s2))
return false
if( substring(s2,concat(s1,s1))
return true
return false
end
자바어:
boolean isRotation(String s1,String s2) {
return (s1.length() == s2.length()) && ((s1+s1).indexOf(s2) != -1);
}
"스택오버플로우 커뮤니티에 물어보고 5분 안에 적어도 4개의 좋은 답변을 얻을 수 있을 것입니다."라고 대답하는 것이 분명 더 좋은 답변입니다.두뇌도 좋지만 해결책을 찾기 위해 다른 사람과 협력할 줄 아는 사람에게 더 높은 가치를 두고 싶다.
또 다른 python 예제(THE 답변에 기반):
def isrotation(s1,s2):
return len(s1)==len(s2) and s1 in 2*s2
다른 사람들이 2차 최악의 시간 복잡도 솔루션을 제출했기 때문에, 나는 (한국 해양 경찰대 알고리즘에 근거한) 선형 솔루션을 추가합니다.
bool is_rotation(const string& str1, const string& str2)
{
if(str1.size()!=str2.size())
return false;
vector<size_t> prefixes(str1.size(), 0);
for(size_t i=1, j=0; i<str1.size(); i++) {
while(j>0 && str1[i]!=str1[j])
j=prefixes[j-1];
if(str1[i]==str1[j]) j++;
prefixes[i]=j;
}
size_t i=0, j=0;
for(; i<str2.size(); i++) {
while(j>0 && str2[i]!=str1[j])
j=prefixes[j-1];
if(str2[i]==str1[j]) j++;
}
for(i=0; i<str2.size(); i++) {
if(j>=str1.size()) return true;
while(j>0 && str2[i]!=str1[j])
j=prefixes[j-1];
if(str2[i]==str1[j]) j++;
}
return false;
}
편집: 인정된 답변은 이것보다 확실히 더 우아하고 효율적입니다.원래 줄을 두 배로 늘리지 않았다면 어떻게 했을까라는 답을 남겼습니다.
난 그냥 폭력적으로 밀어붙일단 말이야.먼저 길이를 확인한 다음 가능한 모든 회전 간격띄우기를 시도합니다.이들 중 문제가 해결되지 않으면 false를 반환하고 문제가 발생한 경우 true를 즉시 반환하십시오.
포인터(C)나 인덱스(Java)를 사용하여 각 문자열에 하나씩 연결하기만 하면 됩니다.한 문자열의 선두와 두 번째 문자열의 현재 후보 회전 오프셋에서 시작하여 필요에 따라 래핑합니다.문자열의 각 지점에서 문자가 동일한지 확인합니다.첫 번째 줄의 끝에 도달하면 끝입니다.
적어도 자바에서는 효율은 떨어지지만 연결은 거의 간단할 것이다.
여기 regex를 재미로 사용하는 방법이 있습니다.
boolean isRotation(String s1, String s2) {
return (s1.length() == s2.length()) && (s1 + s2).matches("(.*)(.*)\\2\\1");
}
어느 문자열에도 없는 특수 딜리미터 문자를 사용할 수 있으면 조금 더 간단하게 할 수 있습니다.
boolean isRotation(String s1, String s2) {
// neither string can contain "="
return (s1 + "=" + s2).matches("(.*)(.*)=\\2\\1");
}
대신 유한 반복으로 룩백을 사용할 수도 있습니다.
boolean isRotation(String s1, String s2) {
return (s1 + s2).matches(
String.format("(.*)(.*)(?<=^.{%d})\\2\\1", s1.length())
);
}
워, 워...왜 다들 이 노래에 열광하는 거야?O(n^2)답할할 수???나는 우리가 여기서 더 잘 할 수 있다고 확신한다.위의 답변에는 다음이 포함됩니다.O(n)에서의 O(n) callloop('서브스트링/인덱스 Of')). 알고리즘을하더라도, 예를 들어 '보다 낫다'와 같은 검색 알고리즘을 사용할 수 있습니다.Boyer-Moore ★★★★★★★★★★★★★★★★★」KMPO(n^2)복사를 합니다.
A O(n)해시 등)는 「라빈 지문」을 합니다. 라빈O(1)sliding window: 해시 문자열 1, 해시 문자열 2 순으로 선택하고 해시 1의 창을 문자열 주위에 이동하여 해시 함수가 충돌하는지 확인합니다.
를 '두 가닥의 DNA를 같은 'DNA를 스캔한다'는 됩니다.O(n^(1+e))(여기서 추측만 하면) 뭐랄까.
마지막으로, 결정론적인 것이 있습니다.O(nlogn)이치기본적으로는 두 현을 한 번 더 돌려보는 것이 아이디어입니다.. 즉, 회전차(회전할 경우)가 됩니다.O(n) 은 두 둘 다입니다.좋은 점은 두 개의 동일한 최대값이 있는 경우 둘 다 유효한 솔루션이라는 것입니다.할 수 때문에, 「FFT」, 「iFFT」가 됩니다.nlogn + nlogn + n + nlogn + n == O(nlogn)
수 가 2^할 수 느린 FFT가 그래도 이 됩니다.2^n은 FFT입니다.O(nlogn)CT 검사
것이,는 100% 이다. 인 것이 , 100% 긍정적이다.O(n)이데올로기 때문에
첫째, 두 줄의 길이가 같은지 확인합니다.그런 다음 C에서 간단한 포인터 반복으로 이를 수행할 수 있습니다.
int is_rotation(char* s1, char* s2)
{
char *tmp1;
char *tmp2;
char *ref2;
assert(s1 && s2);
if ((s1 == s2) || (strcmp(s1, s2) == 0))
return (1);
if (strlen(s1) != strlen(s2))
return (0);
while (*s2)
{
tmp1 = s1;
if ((ref2 = strchr(s2, *s1)) == NULL)
return (0);
tmp2 = ref2;
while (*tmp1 && (*tmp1 == *tmp2))
{
++tmp1;
++tmp2;
if (*tmp2 == '\0')
tmp2 = s2;
}
if (*tmp1 == '\0')
return (1);
else
++s2;
}
return (0);
}
여기 있습니다.O(n)그리고 항상 제자리에 있다. it it를 한다.<문자열 요소의 연산자.물론 내 것은 아니다.여기서 찍었습니다(현장은 광택이 나 있습니다.예전에 한 번인가 본 적이 있는데, 지금은 그런 것을 영어로 찾을 수 없기 때문에, 내가 가지고 있는 것을 보여 줍니다:)
bool equiv_cyc(const string &u, const string &v)
{
int n = u.length(), i = -1, j = -1, k;
if (n != v.length()) return false;
while( i<n-1 && j<n-1 )
{
k = 1;
while(k<=n && u[(i+k)%n]==v[(j+k)%n]) k++;
if (k>n) return true;
if (u[(i+k)%n] > v[(j+k)%n]) i += k; else j += k;
}
return false;
}
것 요.Java:
boolean isRotation(String s1,String s2) {
return (s1.length() == s2.length()) && (s1+s1).contains(s2);
}
Perl에서는 다음 작업을 수행합니다.
sub isRotation {
my($string1,$string2) = @_;
return length($string1) == length($string2) && ($string1.$string1)=~/$string2/;
}
또는 정규식 대신 인덱스 함수를 사용하는 것이 좋습니다.
sub isRotation {
my($string1,$string2) = @_;
return length($string1) == length($string2) && index($string2,$string1.$string1) != -1;
}
이것이 가장 효율적인 방법인지는 확실하지 않지만 비교적 흥미로운 방법일 수 있습니다. Burrows-Wheeler 변환입니다.WP 기사에 따르면 입력의 모든 회전은 동일한 출력을 산출한다.압축과 같은 애플리케이션의 경우 이 방법은 바람직하지 않으므로 원래 회전이 인덱스로 표시됩니다(예: 문서 참조).그러나 회전과 무관하게 단순하게 비교한다면 이상적으로 들릴 것입니다.물론, 반드시 이상적으로 효율적인 것은 아닙니다!
각 문자를 진폭으로 하여 이산 푸리에 변환을 수행합니다.회전만으로 다를 경우 주파수 스펙트럼은 반올림 오차 내와 동일합니다.물론 길이가 2의 거듭제곱이 아니므로 FFT :-)를 수행할 수 없다면 이 방법은 비효율적입니다.
아직 아무도 모듈로 방식을 제안하지 않았습니다. 그래서 한 가지 예를 들어보죠.
static void Main(string[] args)
{
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "ztackoverflow"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "ackoverflowst"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "overflowstack"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "stackoverflwo"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "tackoverflwos"));
Console.ReadLine();
}
public static bool IsRotation(string a, string b)
{
Console.WriteLine("\nA: {0} B: {1}", a, b);
if (b.Length != a.Length)
return false;
int ndx = a.IndexOf(b[0]);
bool isRotation = true;
Console.WriteLine("Ndx: {0}", ndx);
if (ndx == -1) return false;
for (int i = 0; i < b.Length; ++i)
{
int rotatedNdx = (i + ndx) % b.Length;
char rotatedA = a[rotatedNdx];
Console.WriteLine( "B: {0} A[{1}]: {2}", b[i], rotatedNdx, rotatedA );
if (b[i] != rotatedA)
{
isRotation = false;
// break; uncomment this when you remove the Console.WriteLine
}
}
return isRotation;
}
출력:
A: stackoverflow B: ztackoverflow
Ndx: -1
Rotation : False
A: stackoverflow B: ackoverflowst
Ndx: 2
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
Rotation : True
A: stackoverflow B: overflowstack
Ndx: 5
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
Rotation : True
A: stackoverflow B: stackoverflwo
Ndx: 0
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
B: o A[12]: w
Rotation : False
A: stackoverflow B: tackoverflwos
Ndx: 1
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
B: o A[12]: w
B: s A[0]: s
Rotation : False
[편집: 2010-04-12]
piotr은 위의 내 코드의 결함을 알아챘다.문자열의 첫 번째 문자가 두 번 이상 발생하면 오류가 발생합니다.예를들면,stackoverflow에 대해 했습니다.owstackoverflow그것이 사실이어야 할 때 거짓이 되었다.
오류를 발견해 주셔서 감사합니다.
다음은 수정된 코드입니다.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
namespace TestRotate
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "ztackoverflow"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "ackoverflowst"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "overflowstack"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "stackoverflwo"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "tackoverflwos"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "owstackoverfl"));
Console.ReadLine();
}
public static bool IsRotation(string a, string b)
{
Console.WriteLine("\nA: {0} B: {1}", a, b);
if (b.Length != a.Length)
return false;
if (a.IndexOf(b[0]) == -1 )
return false;
foreach (int ndx in IndexList(a, b[0]))
{
bool isRotation = true;
Console.WriteLine("Ndx: {0}", ndx);
for (int i = 0; i < b.Length; ++i)
{
int rotatedNdx = (i + ndx) % b.Length;
char rotatedA = a[rotatedNdx];
Console.WriteLine("B: {0} A[{1}]: {2}", b[i], rotatedNdx, rotatedA);
if (b[i] != rotatedA)
{
isRotation = false;
break;
}
}
if (isRotation)
return true;
}
return false;
}
public static IEnumerable<int> IndexList(string src, char c)
{
for (int i = 0; i < src.Length; ++i)
if (src[i] == c)
yield return i;
}
}//class Program
}//namespace TestRotate
출력은 다음과 같습니다.
A: stackoverflow B: ztackoverflow
Rotation : False
A: stackoverflow B: ackoverflowst
Ndx: 2
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
Rotation : True
A: stackoverflow B: overflowstack
Ndx: 5
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
Rotation : True
A: stackoverflow B: stackoverflwo
Ndx: 0
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
Rotation : False
A: stackoverflow B: tackoverflwos
Ndx: 1
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
Rotation : False
A: stackoverflow B: owstackoverfl
Ndx: 5
B: o A[5]: o
B: w A[6]: v
Ndx: 11
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
Rotation : True
다음은 람다 접근법입니다.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace IsRotation
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "ztackoverflow"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "ackoverflowst"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "overflowstack"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "stackoverflwo"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "owstackoverfl"));
string strToTestFrom = "stackoverflow";
foreach(string s in StringRotations(strToTestFrom))
{
Console.WriteLine("is {0} rotation of {1} ? {2}",
s, strToTestFrom,
IsRotation(strToTestFrom, s) );
}
Console.ReadLine();
}
public static IEnumerable<string> StringRotations(string src)
{
for (int i = 0; i < src.Length; ++i)
{
var sb = new StringBuilder();
for (int x = 0; x < src.Length; ++x)
sb.Append(src[(i + x) % src.Length]);
yield return sb.ToString();
}
}
public static bool IsRotation(string a, string b)
{
if (b.Length != a.Length || a.IndexOf(b[0]) < 0 ) return false;
foreach(int ndx in IndexList(a, b[0]))
{
int i = ndx;
if (b.ToCharArray().All(x => x == a[i++ % a.Length]))
return true;
}
return false;
}
public static IEnumerable<int> IndexList(string src, char c)
{
for (int i = 0; i < src.Length; ++i)
if (src[i] == c)
yield return i;
}
}//class Program
}//namespace IsRotation
다음은 람다 접근법 출력입니다.
Rotation : False
Rotation : True
Rotation : True
Rotation : False
Rotation : True
is stackoverflow rotation of stackoverflow ? True
is tackoverflows rotation of stackoverflow ? True
is ackoverflowst rotation of stackoverflow ? True
is ckoverflowsta rotation of stackoverflow ? True
is koverflowstac rotation of stackoverflow ? True
is overflowstack rotation of stackoverflow ? True
is verflowstacko rotation of stackoverflow ? True
is erflowstackov rotation of stackoverflow ? True
is rflowstackove rotation of stackoverflow ? True
is flowstackover rotation of stackoverflow ? True
is lowstackoverf rotation of stackoverflow ? True
is owstackoverfl rotation of stackoverflow ? True
is wstackoverflo rotation of stackoverflow ? True
아무도 C++ 솔루션을 주지 않았기 때문입니다.여기 있습니다.
bool isRotation(string s1,string s2) {
string temp = s1;
temp += s1;
return (s1.length() == s2.length()) && (temp.find(s2) != string::npos);
}
오페라의 간단한 포인터 회전 기술은 작동하지만, 최악의 경우 실행 시간에는 매우 비효율적입니다.문자열에 여러 개의 긴 반복 문자가 있다고 상상해 보십시오.
S1 = HELLOLOLOLOLO1HELLOLOLOLO2
S2 = HELLOLOLOLOLO2HELLOLOLOLOLO1
"불일치가 있을 때까지 루프한 후 1씩 증가하여 다시 시도"는 계산상으로는 끔찍한 접근법입니다.
플레인 C에서 큰 힘을 들이지 않고 연결접근법을 실행할 수 있음을 증명하기 위해 다음 솔루션을 제시하겠습니다.
int isRotation(const char* s1, const char* s2) {
assert(s1 && s2);
size_t s1Len = strlen(s1);
if (s1Len != strlen(s2)) return 0;
char s1SelfConcat[ 2 * s1Len + 1 ];
sprintf(s1SelfConcat, "%s%s", s1, s1);
return (strstr(s1SelfConcat, s2) ? 1 : 0);
}
이는 O(n) 메모리 사용량(오버헤드)을 희생하면서 실행 시간으로 선형적입니다.
(strstr()의 실장은 플랫폼에 따라 다르지만, 특히 뇌사 상태에 있는 경우에는 항상 Boyer-Moore 알고리즘과 같은 보다 빠른 대체 방법으로 대체할 수 있습니다.)
C#:
s1 == null && s2 == null || s1.Length == s2.Length && (s1 + s1).Contains(s2)
s2가 s1과 연결된 s1의 부분 문자열인지 확인하는 답변이 좋습니다.
우아함을 잃지 않는 최적화를 더하고 싶었습니다.
문자열을 연결하는 대신 조인 뷰를 사용할 수 있습니다(다른 언어에 대해서는 모르지만 C++ Boost에는 사용할 수 있습니다).범위는 이러한 종류의 뷰를 제공합니다).
문자열이 다른 문자열의 서브스트링인지 아닌지는 선형 평균 복잡도(최악의 경우 복잡도는 2차)이므로 이 최적화는 속도를 평균 2배 향상시킵니다.
순수 Java 응답(null 체크 산)
private boolean isRotation(String s1,String s2){
if(s1.length() != s2.length()) return false;
for(int i=0; i < s1.length()-1; i++){
s1 = new StringBuilder(s1.substring(1)).append(s1.charAt(0)).toString();
//--or-- s1 = s1.substring(1) + s1.charAt(0)
if(s1.equals(s2)) return true;
}
return false;
}
그리고 이제 완전히 다른 것을 위해.
문자열이 서로 회전하지 않을 때 제한된 컨텍스트에서 매우 빠른 답변을 원하는 경우
- 두 문자열 모두에서 일부 문자 기반 체크섬(모든 문자 xoring 등)을 계산합니다.시그니처가 다른 경우 문자열은 서로 회전하지 않습니다.
동의하면 실패할 수 있지만 문자열이 일치하지 않는지, 일치하는지 여부를 확인하는 데 문자열 연결과 같은 다른 알고리즘을 사용할 수 있습니다.
또 다른 루비 솔루션은 다음과 같은 답변을 기반으로 합니다.
def rotation?(a, b); a.size == b.size and (b*2)[a]; end
를 사용하여 은 매우 strlen ★★★★★★★★★★★★★★★★★」strpos★★★★
function isRotation($string1, $string2) {
return strlen($string1) == strlen($string2) && (($string1.$string1).strpos($string2) != -1);
}
말인지 strpos는 내부적으로 사용하지만 KMP를 사용하는 경우 이는 시간적으로 선형적입니다.
스트링 중 하나를 반대로 합니다.양쪽의 FFT를 취합니다(단순 정수 시퀀스로 처리).결과를 점 단위로 곱합니다.역 FFT를 사용하여 다시 변환합니다.문자열이 서로 회전하는 경우 결과는 단일 피크를 가집니다. 피크 위치는 문자열이 서로 회전하는 양에 따라 표시됩니다.
왜 이런 거 안 돼?
//is q a rotation of p?
bool isRotation(string p, string q) {
string table = q + q;
return table.IndexOf(p) != -1;
}
물론 Index Of() 함수를 직접 작성할 수 있습니다.그럴지는 잘 모르겠습니다.NET은 순진한 방법 또는 더 빠른 방법을 사용합니다.
순진:
int IndexOf(string s) {
for (int i = 0; i < this.Length - s.Length; i++)
if (this.Substring(i, s.Length) == s) return i;
return -1;
}
고속화:
int IndexOf(string s) {
int count = 0;
for (int i = 0; i < this.Length; i++) {
if (this[i] == s[count])
count++;
else
count = 0;
if (count == s.Length)
return i - s.Length;
}
return -1;
}
편집: 하나씩 문제가 있을 수 있으므로 확인하고 싶지 않습니다.;)
Perl에서는 다음을 수행합니다.
sub isRotation {
return length $_[0] == length $_[1] and index($_[1],$_[0],$_[0]) != -1;
}
int rotation(char *s1,char *s2)
{
int i,j,k,p=0,n;
n=strlen(s1);
k=strlen(s2);
if (n!=k)
return 0;
for (i=0;i<n;i++)
{
if (s1[0]==s2[i])
{
for (j=i,k=0;k<n;k++,j++)
{
if (s1[k]==s2[j])
p++;
if (j==n-1)
j=0;
}
}
}
if (n==p+1)
return 1;
else
return 0;
}
string1string2KMP 알고리즘을 사용하여 KMP가 동작하고 있는지 여부를 확인합니다.string2새로 형성된 문자열에 있습니다.의 시간 는 'KMP'보다 때문에substr.
언급URL : https://stackoverflow.com/questions/2553522/interview-question-check-if-one-string-is-a-rotation-of-other-string