알고리즘 도움말이 필요합니다 (코드 가능)

Question

이 문제에서는 영문 소문자 (a-z)로 구성된 문자열 만 고려합니다. 문자열은 오른쪽에서 왼쪽으로 똑같이 왼쪽에서 오른쪽으로 똑같이 읽는다면 회문입니다. 길이 N의 문자열 S 감안

zaza 
abcd 
abacada 

는 S 슬라이스 지정된 S의 문자열이다

aza 
abba 
abacaba 

이러한 문자열 회문 아니다 :

예를 들어, 이러한 문자열 회문있다 0 ≤ p < q < N과 같이 한 쌍의 정수 (p, q)로 나타낼 수 있습니다. S[p], S[p+1], ..., S[q] 문자로 구성된 문자열이 회문 색인이면 문자열 S의 슬라이스 (p, q)는 회문 변 수입니다. da가 회문,
슬라이스 없기 때문에 abba가 회문,
슬라이스 때문에 예

, 문자열 S = abbacada:

조각 (0, 3) 상동하다 (6, 7) 팔린 드롬 아니다 baca은 회문이 아니기 때문에 회문이 아닙니다. bb은 회문 계이므로
조각 (1, 2)은 회문입니다.

---

함수 길이 N 문자의 문자열 S 주어진 함수 반환한다 -1 수가 100,000,000보다 크면 S. 팔린 드롬의 슬라이스의 개수를 리턴 int solution(const string &S); 적는다.

예를 들어, S = baababa 문자열의 경우 정확히 6 개의 회문문이 있기 때문에 함수는 6을 반환해야합니다. 즉 : (0, 3), (1, 2), (2, 4), (2, 6), (3, 5), (4, 6).

다음과 같이 가정하십시오.
- N은 [0..200,000] 범위의 정수입니다.
- 문자열 S는 소문자 (a-z)로만 구성됩니다.

복잡도 :
- 최악의 경우의 예상 시간 복잡도는 O (N)입니다.
- 예상 최악의 공간 복잡도는 O (N) (입력 인수에 필요한 저장소를 계산하지 않음)입니다.

여기 내 솔루션입니다 : 큰 문자열

int palindrom(const string &S, int startIndex,int endIndex, int counter=0) 
{ 
    bool equals = true; 
    if (endIndex - startIndex < 1) 
     return counter; 
    for(int i = startIndex,j = endIndex;i<j; ++i, --j) 
    { 
     equals = S[i] == S[j]; 
     if (!equals) break; 
    } 
    if (equals) counter++; 
    counter = palindrom(S,startIndex,endIndex-1,counter); 
    return counter; 
} 

int solution(const string &S) 
{ 
    int length = S.size(); 
    int counter = 0; 
    if (length > 20000) return -1; 
    for(int i=0; i < length-1; i++) 
    { 
     counter += palindrom(S,i,length-1); 
     if (counter > 100000000) return -1; 
    } 
    return counter; 
} 

S.size()> 난 항상 런타임 오류 3000 (시간이 3 초 만 솔루션 미만 이초에서 작동해야 더 다음을 의미)! 어떤 제안?

오케이! 재귀없이

main(){cout<<solution("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");} 

Answer 1

내가 할 것

#include <string> 
#include <iostream> 

typedef std::string::const_iterator P; 

bool is_palindrom(P begin, P end) { 
    while (begin < end) { 
     if (*begin != *end) 
      return false; 
     ++begin; 
     --end; 
    } 
    return true; 
} 

int count_palindroms(const std::string &s) { 
    int c = 0; 
    P left = s.begin(); 
    while (left < s.end()) { 
     P right = left + 1; // because length palindrome > 1 
     while (right < s.end()) { 
      if (is_palindrom(left, right)) { 
       //std::cout << left - s.begin() << ' ' << right - s.begin() << std::endl; 
       c++; 
       if (c > 100000000) 
        return -1; 
      } 
      ++right; 
     } 
     ++left; 
    } 
    return c; 
} 

int main(int , char *[]) 
{ 
    std::cout << count_palindroms("baababa") << std::endl; 
    return 0; 
} 

Answer 2

그것은 내 PC에서 잘 작동합니다 및 주요 기능은 같은입니다. 여기서 실제로하는 것은 원래 문자열의 모든 하위 문자열을 검사하고 그 위에 반복적 인 함수를 실행하는 것입니다. @PeterT가 언급했듯이, 당신은 아마도 당신이 갇혀있는 곳의 최대 깊이에 도달했을 것입니다.

내가 호출 스택을 사용하지 않는 할 것입니다,하지만 하나가 내 자신의 고집을 사용하거나 같은 몇 가지 간단한 문자열 함수를 사용하는 예에 대한

std::string s = "aba"; 
std::string s1 = std::string(s.rbegin(), s.rend()); 
if (s == s1) 
{ 
///... 
} 

.

시간 복잡성에 관해서 - here을 읽을 수 있으므로 o (n)에서 모두 확인할 수는 없습니다.

Answer 3

단순히 (알고리즘의 작은 변화) 재귀를 삭제합니다 :

int palindrom(const string &S, int startIndex, int endIndex, int counter = 0) 
{ 
    for (int k = endIndex; k > startIndex; --k) { 
     bool equals = true; 
     for (int i = startIndex, j = k; i < j; ++i, --j) 
      if (S[i] != S[j]) { 
       equals = false; 
       break; 
      } 
     if (equals) 
      counter++; 
    } 
    return counter; 
}