Pomoc algorytmu jest potrzebna (Codility)

Question

W tym problemie rozważamy tylko ciągi składające się z małych liter angielskich (a-z). Ciąg jest palindromem, jeśli czyta dokładnie to samo od lewej do prawej, tak jak od prawej do lewej.

Na przykład, te słowa są palindromów:

aza 
abba 
abacaba 

Te sekwencje nie palindromów:

zaza 
abcd 
abacada 

względu ciąg S o długości N, plaster S jest podciąg S określona przez parę liczb całkowitych (p, q), tak że 0 ≤ p < q < N. Plasterek (p, q) napisu S jest palindromiczny, jeśli ciąg składający się z liter S[p], S[p+1], ..., S[q] jest palindromem.

Na przykład, w ciągu S = abbacada:

slice (0, 3) palindromowe ponieważ abba jest palindrom,
plaster (6, 7) nie jest palindromowe ponieważ da jest palindrom,
plaster (2, 5) nie jest palindromiczny, ponieważ baca nie jest palindromem,
plaster (1, 2) jest palindromiczny, ponieważ bb jest palindromem.

---

Dodaj funkcję int solution(const string &S); że dany łańcuch S o długości n litery powraca liczbę palindromicznych plastry S. Funkcja powinna powrócić -1 Jeśli liczba ta jest większa niż 100.000.000.

Na przykład w przypadku ciągu znaków S = baababa funkcja powinna powrócić 6, ponieważ dokładnie sześć jej wycinków jest palindromicznych; a mianowicie: (0, 3), (1, 2), (2, 4), (2, 6), (3, 5), (4, 6).

Załóżmy, że:
- N jest liczbą całkowitą w zakresie [0..20.000];
- ciąg S składa się tylko z małych liter (a-z).

Kompleksowość:
- oczekiwana najgorsza złożoność czasu to O (N);
- oczekiwana złożoność najgorszego przypadku to O (N) (nie licząc pamięci wymaganej dla argumentów wejściowych).

Oto moje rozwiązanie:

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; 
} 

z dużych ciągów S.size()> 3000 Zawsze dostać błąd wykonania (czyli czas jest więcej niż 3 sek ale rozwiązanie powinno działać w czasie krótszym niż 2 sekundy)! Jakieś sugestie?

ok! a główną funkcją jest coś takiego:

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

Answer 1

bym bez rekursji

#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

Działa prawidłowo na moim komputerze. To, co aktualnie robisz, polega na sprawdzeniu każdego ciągu podrzędnego oryginalnego łańcucha i uruchomieniu na nim funkcji rekurencyjnej. Jak wspomniałeś @PeterT prawdopodobnie osiągniesz maksymalną głębokość utknięcia.

Co bym zrobił nie używać stosu wywołań, ale albo użyć własnego zatrzymany lub użyj kilka prostych funkcji ciągów jak:

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

dla przykładu.

Jeśli chodzi o złożoność czasu - jak można przeczytać here nie można sprawdzić ich wszystkich w o (n).

Answer 3

Chciałbym po prostu usunąć rekurencji (z niewielką zmianą algorytmu):

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; 
}