Longest Palindromic Sub-string

Question:
find longest palindromic substring.
Answer:

#include <cstdlib>
#include <iostream>
#include <ctime>

using namespace std;

/* 0~9, a~z, A~z */
void randstring(int n, char* s) {
  int fn = rand() % n;
  if (fn <= n/2)
    fn = (n+1) / 2;
  for (int i = 0; i < fn; i++) {
    int t = rand() % 3;
    char c;
    if (t == 0)
      s[i] = '0' + (rand()%10);
    else if (t == 1)
      s[i] = 'a' + (rand()%26);
    else
      s[i] = 'A' + (rand()%26);
  }
  for (int i = fn; i < n; i++) {
    s[i] = s[rand()%fn];
  }
}

int main() {
  srand(time(0));
  int n = 20;
  char* s = new char[n+1];
  s[n] = '\0';
  randstring(n, s);
  cout << s << endl;
  int n2 = (n+1)*2 + 1;
  char* ns = new char[n2];
  ns[0] = '$';
  ns[1] = '#';
  int j;
  int i;
  for (i = 0, j = 2; i < n; i++) {
    ns[j] = s[i];
    ns[++j] = '#';
    j++;
  }
  ns[j] = '#';
  ns[n2-1] = '\0';
  cout << ns << endl;
  int* p = new int[n2];
  for (i = 0; i < n2; i++)
    p[i] = 0;
  int mx = 0;
  int id = 0;
  int pid = 0;
  int pi = 0;
  for (i = 1; i < n2; i++) {
    p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;
    while (ns[i + p[i]] == ns[i-p[i]]) p[i]++;
    if ((i + p[i]) > mx) {
      mx = i + p[i];
      id = i;
    }
    if (p[i] > pid) {
      pid = p[i];
      pi = i;
    }
  }
  cout << " ";
  for (i = 1; i < n2-1; i++)
    cout << p[i];
  cout << endl;
  cout << pid << " " << pi << endl;
  if (pid > 2) {
    for (i = pi - p[pi] + 1; i < pi + p[pi]; i++)
      if (ns[i] != '#')
        cout << ns[i];
  }
  cout << endl;
  delete []s;
  delete []ns;
  delete []p;
  return 0;
}

Subscribe to Post, Code and Quiet Time.

Don’t miss out on the latest issues. Sign up now to get access to the library of members-only issues.
jamie@example.com
Subscribe