효율적인 알고리즘과 C++의 문자열에서주기를 찾는 코드는 무엇입니까?

예를 들어 "12345123451234512345"에서 "12345"를 찾는 효율적인 알고리즘은 무엇입니까?효율적인 알고리즘과 C++의 문자열에서주기를 찾는 코드는 무엇입니까?

C++로 코딩.

감사합니다.

2010-12-04 B Seven

이 숙제가 있습니까? 그렇다면 말하기가 예의 일 것입니다. 또한 "teh codez를 보내십시오"라는 질문은 좋은 답변을 거의 얻지 못합니다. 너 뭐 해봤 니? 어떤 문제에 빠지셨습니까? –

질문은 "주기"가 무엇인지, 그리고 문자열에 문자열이있는 지에 대해서도 충분하지 않습니다. – zwol

이 번호 만입니까? 사이클이 얼마나 큰지 당신은 단서가 있습니까? 아니면 반복 횟수? – Falmarri

당신의 하나의 예에 간다 :

12345123451234512345 반환 12345

나는 당신이 원하는 것은 건초 더미를 완료하기 위해 반복 가능한 가장 긴 바늘을 찾는 것입니다 생각, 즉 1212121212 =>12, 444 =>4 등등.

가장 간단한 해결책은 첫 번째 문자를 선택하고 일치하는 문자열 비교를 실행하는 것입니다. 어느 지점에서든 불일치가있는 경우 처음 두 문자를 선택하고 전체 문자열을 비교하는 등의 작업을 수행하여 창 크기가 문자열의 절반보다 커질 때까지 실행합니다.

복잡성 (N^2)

당신은 당신이 즉 창 크기는 문자열의 길이의 약수가 될 수 문자열의 길이에 따라 선택하는 창 크기를 최적화 할 수 있습니다 O를해야합니다.

2010-12-04 05:37:08

가능한 한 긴 시간이 지난 경우 문자열 "1234512345"가 예제에서 두 번 반복되지 않습니까? – abelenky

@abelenky : 윈도우가 크기 1에서부터 증가합니다. 알고리즘은 전체 문자열과 일치하므로 12345에서 멈출 것입니다. =) –

for 444는 44가 아닙니다. –

답변