Counting Palindrome Substrings ?

Discussion in 'C++' started by Andrew Tomazos, Feb 5, 2011.

  1. We want to count how many different N character strings over a 26-
    letter alphabet contain K or more M character palindrome substrings.

    For example, how many 3 character strings over a 26-letter alphabet
    contain 1 or more 2 character palindrome substrings?

    Well there is...

    { AAA, BAA, CAA, DAA, ..., ZBB, CCB, DDB, EEB, ..., YZZ, ZZZ }

    ....a total of 1326 different 3 character strings that contain a 2
    character palindrome.

    The brute force approach would be to iterate over all possible N
    character strings and test whether they have K or more M character
    palindrome substrings...

    #include <string>

    using namespace std;

    // is [begin,end) a palindrom?
    template <typename iterator>
    bool isPalindrome(iterator begin, iterator end)
    {
    while (begin + 1 < end)
    {
    if (*begin != *(end - 1))
    return false;

    begin++;
    end--;
    }

    return true;
    }

    // does s have K or more M character palindrom substrings?
    bool hasKPalindromeSubstrings(const string& s, int M, int K)
    {
    int n = 0;
    for (int i = 0; i <= s.size() - M; i++)
    {
    if (isPalindrome(s.begin() + i, s.begin() + i + M))
    n++;
    }

    return n >= K;
    }

    // increment string along 'AAAAA', 'AAAAB' ... 'ZZZZZ', return false
    on 'ZZZZZ'
    bool incrementString(string& s)
    {
    for (int i = 0; i < s.size(); i++)
    {
    if (s != 'Z')
    {
    s++;
    return true;
    }
    else
    s = 'A';

    }
    return false;
    }

    // count how many N character strings have K or more M character
    palindrom substrings
    long long countPalindromeSubstrings(int N, int M, int K)
    {
    string s(N, 'A');

    long long t = 0;
    do
    {
    if (hasKPalindromeSubstrings(s, M, K))
    t++;
    }
    while (incrementString(s));
    return t;
    }

    int main()
    {
    cout << countPalindromSubstrings(3,2,1) << endl; // prints 1326
    }

    Clearly this is algorithm is about O(26^N). Can anyone think of a
    significantly faster way to do it? Perhaps there is some cool
    combinatoric trick or some "recursive reasoning" or a closed form etc?

    Thanks,
    Andrew.
    Andrew Tomazos, Feb 5, 2011
    #1
    1. Advertising

  2. Andrew Tomazos

    Ben Pfaff Guest

    Andrew Tomazos <> writes:

    > We want to count how many different N character strings over a 26-
    > letter alphabet contain K or more M character palindrome substrings.
    >
    > For example, how many 3 character strings over a 26-letter alphabet
    > contain 1 or more 2 character palindrome substrings?
    >
    > Well there is...
    >
    > { AAA, BAA, CAA, DAA, ..., ZBB, CCB, DDB, EEB, ..., YZZ, ZZZ }
    >
    > ...a total of 1326 different 3 character strings that contain a 2
    > character palindrome.


    There are 26 possible 2-character palindromes over a 26-letter
    alphabet. There are 51 ways to embed each of these into a
    3-character string (each can be preceded or followed by any
    letter, but 2 of those are indistinguishable). Hence there are
    26 * 51 == 1326 possibilities, as you say.

    I suspect that this line of reasoning can be extended to larger
    numbers, but I haven't tried.
    --
    Ben Pfaff
    http://benpfaff.org
    Ben Pfaff, Feb 5, 2011
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Lorin Leone

    Palindrome (HELP)

    Lorin Leone, Nov 12, 2003, in forum: C++
    Replies:
    4
    Views:
    995
    Chris Theis
    Nov 13, 2003
  2. Tung Chau
    Replies:
    1
    Views:
    461
    SM Ryan
    Aug 6, 2004
  3. Tung Chau
    Replies:
    0
    Views:
    365
    Tung Chau
    Aug 6, 2004
  4. Michele Dondi
    Replies:
    0
    Views:
    163
    Michele Dondi
    Nov 15, 2007
  5. edwardfredriks

    counting up instead of counting down

    edwardfredriks, Sep 6, 2005, in forum: Javascript
    Replies:
    6
    Views:
    188
    Dr John Stockton
    Sep 7, 2005
Loading...

Share This Page