Find All Palindrome Substrings

Posted on

This article provides the code to find all palindrome substrings in a given string.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// Find all palindrome substrings in a given string
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------
#include <iostream>
#include <string>
#include <cstdlib>
#include <time.h>

using namespace std;

string s = "abcacbbbca";   // string to be analyzed
const int N = 10;          // length of s

int main()
{
    int i, j, k,   // iterators
    rp,        // length of 'palindrome radius'
    R[2][N+1]; // table for storing results (2 rows for odd- and even-length palindromes

    // print s first

    cout << s << endl;

    // ...then search for palindromes

    s = "@" + s + "#"; // insert 'guards' to iterate easily over s

    for (j = 0; j <= 1; j++)
    {
        R[j][0] = rp = 0; i = 1;
        while(i <= N)
        {
            while(s[i - rp - 1] == s[i + j + rp]) rp++;
            R[j][i] = rp;
            k = 1;
            while((R[j][i - k] != rp - k) && (k < rp))
            {
                R[j][i + k] = min(R[j][i - k],rp - k);
                k++;
            }
            rp = max(rp - k,0);
            i += k;
        }
    }

    s = s.substr(1,N); // remove 'guards'

    // print the results

    for (i = 1; i <= N; i++)
    {
        for (j = 0; j <= 1; j++)
            for (rp = R[j][i]; rp > 0; rp--)
            {
                for(k = 1; k < i - rp; k++) cout << " ";
                cout << s.substr(i - rp - 1,2 * rp + j) << endl;
            }
    }
    cout << endl;
    return 0;
}

Output:

1
2
3
4
5
6
7
8
abcacbbbca
 bcacb
  cac
     bb
   acbbbca
    cbbbc
     bbb
      bb