codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
// 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 = "aaaaaaaaaa"; // 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; }
Private
[
?
]
Run code
Submit