### Well, I hate typing up an answer to find a question deleted.

OP: Stuff about finding palindromes in a string.

Response:
You must first think about how to solve the problem. (You are jumping into the code too soon.)

ahhahha

How would you (a human) go about finding all the palindromes?

Obviously, I would first check to see if the entire thing is a palindrome. (It is.)
I can add that to my list of palindromes.

Now to find smaller palindromes. This is where things become interesting. How many smaller strings (two characters or longer) can you find in the string?
I can find a lot.

ahhahh
ahhah
ahha
ahh
ah
hhahha
hhahh
hhah
hha
hh
hahha
hahh
hah
ha
ahha
ahh
ah
hha
hh
ha

See how I did that? Each time I advanced a letter, I went through all possible lengths from that letter.

So, which of these are palindromic?

• One from the first set: ahha
• Only one of the second set: hhahh
• One of the third set: hah
• One from the fourth set: ahha
• One of the fifth set: hh
• None of the sixth set

This is convenient. Notice that not all sets will have palindromes. (Your source string makes most of them have one, but this is not true of most source strings.)

I have at this point found the list of all palindromes in the string:

ahhahha
ahha
hhahh
hah
ahha
hh

(The fifth one we found is the same as the second. We can ignore it.)

At this point there is only the question of how many times each of these palindromes appear in the original string. I can easily count them, again checking for each possible position from the first to the last:

"ahhahha"
ahhahha — 1 time

"ahhahha"
ahha
ahha — 2 times

"ahhahha"
hhahh — 1 time

"ahhahha"
hah — 1 time

"ahhahha"
hh
hh — 2 times

In fact, I could have gathered the information from the last two steps at the same time. As a human, I would likely have a paper that looks something like:

ahhahha   1
ahha      1 2
hhahh     1
hah       1
hh        1 2

This is a clue that you can probably do the same thing in your program.

────────────────────

Great! Now we can get down to writing some code.

The first thing we need to consider is how we are going to store our collection of palindrome counts. Just as we have on our paper above, we need:

• the palidrome
• the number of times it appears

The technical term for this is a histogram. In C++ this is exactly what the std::map<> container is for. It can be used like this:

 ``123456`` ``````// counts = map std::map counts; // mark palindrome "ahha" as appearing one more time than before counts["ahha"] += 1; // (at this point "ahha" has been found 1 time) ``````

If you cannot use std::map<>, you can easily use another construct, such as an array or pair of arrays:

 ``1234567891011121314151617181920212223242526272829`` ``````// Here is our item struct item { string name; int count; }; // Here is our histogram item counts[ 100 ]; int ncounts = 0; // Updating the histogram takes more work, // because we must now find or add the item ourselves: // (find it) int n = 0; while (n < ncounts) { if (counts[n].name == "ahha") break; n++; } // (update it) if (n < ncounts) { counts[n].count += 1; } // (or add it) else { counts[n].name = "ahha"; counts[n].count = 1; ncounts += 1; }``````

The “find it” code could easily go into a function.
The “add or update it” code could also be a function.

 ``12`` ``````int n = find_item( counts, ncounts, "ahha" ); ncounts = add_or_update_item( counts, ncounts, n, "ahha" );``````

────────────────────

Finally! Now we have some structure to work with. All that is left is to put the pieces together.

• Create your (empty) histogram and get a string from the user.

• Next, use some loops to look through all the possible substrings in your string.
Each time the substring is a palindrome:
• Find the number of times that substring appears in your input string.
(You know it appears at least once.)
• Add the string and the number of times it appears to your histogram.

• When done, your histogram contains all the information you need.

(If you used std::map<> for your histogram, you can print it with the following. The “first” thing in the pair is the palindrome string, and the “second” is the count.)

 ``12`` ``````for (auto pair : counts) std::cout << pair.first << " - " << pair.second << " time(s).\n";``````

(If you used the array, just use a loop:)

 ``12`` ``````for (int n = 0; n < ncounts; n++) std::cout << counts[n].name << " - " << counts[n].count << " times(s).\n";``````

Well, that should be enough to get you going. Remember, you will need a nested loop to enumerate all substrings (outer loop for where the first letter starts, inner loop for the length of the substring). Use the std::string::substr() method to get the pieces of the string. For example:

 ``1234`` ``````std::string s = "palindrome"; int first = 4; int length = 3; std::cout << s.substr( first, length ) << "\n"; // prints "ndr" ``````

Use a little math to get the length of the largest substring from first:

s.length() - first

The length of the smallest substring is 2, of course. Pay attention to the end of the string. (Can first ever be s.size() - 1?)

So there!
i cant understand what you are saying :)
The original poster asked about finding all instances of a palindrome in an input string.
I typed a (large) response.
OP deleted his post before I could submit.
Topic archived. No new replies allowed.