Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Counting Palindrome Substrings ?

Reply
Thread Tools

Counting Palindrome Substrings ?

 
 
Andrew Tomazos
Guest
Posts: n/a
 
      02-05-2011
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[i] != 'Z')
{
s[i]++;
return true;
}
else
s[i] = '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.
 
Reply With Quote
 
 
 
 
Ben Pfaff
Guest
Posts: n/a
 
      02-05-2011
Andrew Tomazos <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Counting the repetition count of repeated substrings Michele Dondi Perl Misc 0 11-15-2007 03:38 PM
counting up instead of counting down edwardfredriks Javascript 6 09-07-2005 03:30 PM
Replacing palindrome substrings of an input string with a given string Tung Chau C Programming 1 08-06-2004 07:27 PM
Replacing palindrome substrings of an input string with a given string. Any effecient algorithm? Tung Chau C Programming 0 08-06-2004 10:18 AM
Palindrome (HELP) Lorin Leone C++ 4 11-13-2003 08:11 AM



Advertisments