Có bao nhiêu palindromes có thể được tạo thành bằng cách chọn các ký tự từ một chuỗi?

Question

Tôi đăng nội dung này thay mặt cho một người bạn vì tôi cho rằng điều này khá thú vị:

Lấy chuỗi "abb". Bằng cách bỏ ra bất kỳ số chữ cái nào nhỏ hơn độ dài của chuỗi, chúng tôi kết thúc với 7 chuỗi.

a b b ab ab bb abb

Trong số 4 là palindromes.

Tương tự cho chuỗi

"hihellolookhavealookatthispalindromexxqwertyuiopasdfghjklzxcvbnmmnbvcxzlkjhgfdsapoiuytrewqxxsoundsfamiliardoesit"

(chiều dài 112 string) 2^112-1 chuỗi có thể được hình thành.

Trong số này có bao nhiêu là palindromes ??

Dưới đây là triển khai của anh ấy (trong C++, C cũng tốt). Nó khá chậm với những từ rất dài; anh ta muốn biết thuật toán nhanh nhất có thể cho điều này (và tôi cũng tò mò: D).

#include <iostream> 
#include <cstring> 

using namespace std; 



void find_palindrome(const char* str, const char* max, long& count) 
{ 
    for(const char* begin = str; begin < max; begin++) { 
     count++; 
     const char* end = strchr(begin + 1, *begin); 
     while(end != NULL) { 
      count++; 
      find_palindrome(begin + 1, end, count); 
      end = strchr(end + 1, *begin); 
     } 
    } 
} 


int main(int argc, char *argv[]) 
{ 
    const char* s = "hihellolookhavealookatthis"; 
    long count = 0; 

    find_palindrome(s, strlen(s) + s, count); 

    cout << count << endl; 
} 

Answer 1

Trước hết, giải pháp của bạn bè dường như có một lỗi từ strchr có thể tìm kiếm qua max. Ngay cả khi bạn sửa lỗi này, giải pháp cũng đúng theo thời gian.

Để có giải pháp nhanh hơn, bạn có thể sử dụng dynamic programming để giải quyết vấn đề này trong thời gian O (n^3). Điều này sẽ yêu cầu bộ nhớ bổ sung O (n^2). Lưu ý rằng đối với các chuỗi dài, thậm chí int-bit 64 bit như tôi đã sử dụng ở đây sẽ không đủ để giữ giải pháp.

#define MAX_SIZE 1000 
long long numFound[MAX_SIZE][MAX_SIZE]; //intermediate results, indexed by [startPosition][endPosition] 

long long countPalindromes(const char *str) { 
    int len = strlen(str); 
    for (int startPos=0; startPos<=len; startPos++) 
     for (int endPos=0; endPos<=len; endPos++) 
      numFound[startPos][endPos] = 0; 

    for (int spanSize=1; spanSize<=len; spanSize++) { 
     for (int startPos=0; startPos<=len-spanSize; startPos++) { 
      int endPos = startPos + spanSize; 
      long long count = numFound[startPos+1][endPos]; //if str[startPos] is not in the palindrome, this will be the count 
      char ch = str[startPos]; 

      //if str[startPos] is in the palindrome, choose a matching character for the palindrome end 
      for (int searchPos=startPos; searchPos<endPos; searchPos++) { 
       if (str[searchPos] == ch) 
        count += 1 + numFound[startPos+1][searchPos]; 
      } 

      numFound[startPos][endPos] = count; 
     } 
    } 
    return numFound[0][len]; 
} 

Giải thích:

Mảng numFound[startPos][endPos] sẽ giữ số palindromes chứa trong chuỗi với chỉ số startPos để endPos.

Chúng tôi đi qua tất cả các cặp chỉ mục (startPos, endPos), bắt đầu từ các nhịp ngắn và chuyển sang các chỉ mục dài hơn. Đối với mỗi cặp như vậy, có hai tùy chọn:

1. Ký tự tại str[startPos] không nằm trong palindrome. Trong trường hợp đó, có numFound[startPos+1][endPos] palindromes có thể có - một số mà chúng tôi đã tính toán rồi.

2. ký tự tại str[startPos] nằm trong palindrome (lúc bắt đầu). Chúng tôi quét qua chuỗi để tìm một ký tự phù hợp để đặt ở cuối palindrome. Đối với mỗi ký tự như vậy, chúng tôi sử dụng kết quả đã tính toán trong numFound để tìm số khả năng cho palindrome bên trong.

EDIT:

• Làm rõ: khi tôi nói "số palindromes chứa trong một chuỗi", điều này bao gồm chuỗi con không tiếp giáp. Ví dụ, palindrome "aba" được chứa trong "abca".

• Có thể giảm mức sử dụng bộ nhớ xuống O (n) bằng cách tận dụng thực tế rằng việc tính toán numFound[startPos][x] chỉ yêu cầu kiến ​​thức về numFound[startPos+1][y] cho tất cả các y. Tôi sẽ không làm điều này ở đây vì nó làm phức tạp mã một chút.

• Danh sách các chỉ mục tạo trước có chứa mỗi chữ cái có thể làm cho vòng lặp bên trong nhanh hơn, nhưng nó vẫn sẽ là tổng thể O (n^3).

Answer 2

Hmmmmm, tôi nghĩ rằng tôi sẽ đếm lên như thế này:

Mỗi nhân vật là một palindrome trên riêng của nó (trừ ký tự lặp đi lặp lại).
Mỗi cặp cùng một ký tự.
Mỗi cặp của cùng một ký tự, với tất cả các palindromes kẹp ở giữa có thể được thực hiện từ chuỗi giữa lặp lại.
Áp dụng đệ quy.

Điều này có vẻ là những gì bạn đang làm, mặc dù tôi không chắc chắn bạn không tính hai lần các trường hợp cạnh với các ký tự lặp lại.

Vì vậy, về cơ bản, tôi không thể nghĩ ra một cách tốt hơn.

EDIT:
Suy nghĩ thêm một số, Có thể cải thiện bộ nhớ đệm, vì đôi khi bạn đếm palindromes trong cùng một chuỗi con nhiều lần. Vì vậy, tôi cho rằng điều này chứng minh rằng chắc chắn có một cách tốt hơn.

Answer 3

Có bất kỳ số dặm nào trong việc thực hiện truyền tải ban đầu và xây dựng chỉ mục tất cả các lần xuất hiện của từng ký tự.

h = { 0, 2, 27} 
i = { 1, 30 } 
etc. 

Bây giờ làm việc từ bên trái, h, chỉ các palidromes có thể là 3 và 17, hiện char [0 + 1] == char [3 -1] v.v ... có palindrome. không char [0 + 1] == char [27 -1] không, Không cần phân tích thêm về char [0].

Chuyển sang char [1], chỉ cần dụ char [30 -1] và vào trong. Sau đó, có thể có được thông minh, khi bạn đã xác định palindrome chạy từ vị trí x-> y, tất cả các tập con bên trong được biết đến palindromes, do đó chúng tôi đã xử lý một số mục, có thể loại bỏ những trường hợp đó sau khi kiểm tra.

Answer 4

Tôi không chắc chắn nhưng bạn có thể thử sự cố màu trắng. Vấn đề này remined tôi về vấn đề này: O(nlogn) Algorithm - Find three evenly spaced ones within binary string

Chỉ 2cents tôi

Answer 5

Giải pháp của tôi sử dụng O(n) bộ nhớ và O(n^2) thời gian, nơi n là chuỗi dài:

palindrome.c:

#include <stdio.h> 
#include <string.h> 

typedef unsigned long long ull; 

ull countPalindromesHelper (const char* str, const size_t len, const size_t begin, const size_t end, const ull count) { 
    if (begin <= 0 || end >= len) { 
    return count; 
    } 
    const char pred = str [begin - 1]; 
    const char succ = str [end]; 
    if (pred == succ) { 
    const ull newCount = count == 0 ? 1 : count * 2; 
    return countPalindromesHelper (str, len, begin - 1, end + 1, newCount); 
    } 
    return count; 
} 

ull countPalindromes (const char* str) { 
    ull count = 0; 
    size_t len = strlen (str); 
    size_t i; 
    for (i = 0; i < len; ++i) { 
    count += countPalindromesHelper (str, len, i, i, 0); // even length palindromes 
    count += countPalindromesHelper (str, len, i, i + 1, 1); // odd length palindromes 
    } 
    return count; 
} 

int main (int argc, char* argv[]) { 
if (argc < 2) { 
    return 0; 
} 
const char* str = argv [1]; 
ull count = countPalindromes (str); 
printf ("%llu\n", count); 
return 0; 
} 

---

Cách sử dụng:

$ gcc palindrome.c -o palindrome 
$ ./palindrome myteststring 

---

EDIT: tôi không nhận định các vấn đề như các phiên bản chuỗi con giáp của vấn đề. Bây giờ cho rằng một trong những muốn tìm palindrome đếm cho phiên bản không tiếp giáp, tôi mạnh mẽ nghi ngờ rằng người ta chỉ có thể sử dụng một phương trình toán học để giải quyết nó cho số lượng ký tự riêng biệt và số lượng nhân vật tương ứng của họ.

Answer 6

Đây là một program for finding all the possible palindromes trong một chuỗi được viết bằng cả Java và C++.

Answer 7

Tôi có một cách có thể làm điều đó trong O (N^2) thời gian và O (1) không gian, tuy nhiên tôi nghĩ rằng phải có những cách khác tốt hơn.

ý tưởng cơ bản là palindrome dài phải chứa palindromes nhỏ, vì vậy chúng tôi chỉ tìm kiếm kết quả tối thiểu, có nghĩa là hai loại tình huống: "aa", "aba". Nếu chúng tôi tìm thấy một trong hai, sau đó mở rộng để xem nếu nó là một phần của một palindrome dài.

int count_palindromic_slices(const string &S) { 
     int count = 0; 

     for (int position=0; position<S.length(); position++) { 
      int offset = 0; 

      // Check the "aa" situation 
      while((position-offset>=0) && (position+offset+1)<S.length() && (S.at(position-offset))==(S.at(position+offset+1))) { 
       count ++; 
       offset ++; 
      } 

      offset = 1; // reset it for the odd length checking 
      // Check the string for "aba" situation 
      while((position-offset>=0) && position+offset<S.length() && (S.at(position-offset))==(S.at(position+offset))) { 
       count ++; 
       offset ++; 
      } 
     } 
     return count; 
    } 

Ngày 14 tháng 6 năm 2012 Sau khi điều tra, tôi tin rằng đây là cách tốt nhất để làm điều đó. nhanh hơn câu trả lời được chấp nhận.

Answer 8

int main() 
{ 
    string palindrome; 

    cout << "Enter a String to check if it is a Palindrome"; 

    cin >> palindrome; 

    int length = palindrome.length(); 

    cout << "the length of the string is " << length << endl; 

    int end = length - 1; 
    int start = 0; 
    int check=1; 

    while (end >= start) { 
     if (palindrome[start] != palindrome[end]) { 
      cout << "The string is not a palindrome"; 
      check=0; 
      break; 
     } 
     else 
     { 
      start++; 
      end--; 

     } 

    } 
    if(check) 
    cout << "The string is a Palindrome" << endl; 

} 

Answer 9

public String[] findPalindromes(String source) { 

    Set<String> palindromes = new HashSet<String>();   
    int count = 0; 
    for(int i=0; i<source.length()-1; i++) {    
     for(int j= i+1; j<source.length(); j++) {    
      String palindromeCandidate = new String(source.substring(i, j+1)); 
      if(isPalindrome(palindromeCandidate)) { 
       palindromes.add(palindromeCandidate);     
      } 
     } 
    } 

    return palindromes.toArray(new String[palindromes.size()]);  
} 

private boolean isPalindrome(String source) { 

    int i =0; 
    int k = source.length()-1;  
    for(i=0; i<source.length()/2; i++) {    
     if(source.charAt(i) != source.charAt(k)) { 
      return false; 
     } 
     k--; 
    }  
    return true; 
}