Circular Palindromes


Problem Statement :


A palindrome is a string that reads the same from left to right as it does from right to left.

Given a string, , S of N lowercase English letters, we define a k-length rotation as cutting the first  kcharacters from the beginning of S and appending them to the end of S. For each S, there are N possible k-length rotations (where 0  <=  K  <  N ). 

See the Explanation section for examples.

Given N and S, find all N  k-length rotations of S; for each rotated string, Sk, print the maximum possible length of any palindromic substring of Sk on a new line.


Input Format

The first line contains an integer, N (the length of S ).
The second line contains a single string, S.


Constraints


1   <=   N   <=  5* 10^5
0  <=    K   <  N
S is  comprised of lower case English letters.

Output Format

There should be N  lines of output, where each line k contains an integer denoting the maximum length of any palindromic substring of rotation Sk.


Solution :



title-img 


                            Solution in C :

In     C++  :







#include <algorithm>
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(i, x) for(type(x) i = (x).begin(); i != (x).end(); i++)
#define hash ___hash

typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + 333;

const int N = 2e6 + 5;

int n;
char s[N];
bool h[N];
int go_odd[N], go_even[N], tmp[N << 1], rad[N << 1], ans[2][N];

void manacher() {
    memset(tmp, 0, sizeof(tmp));
    memset(rad, 0, sizeof(rad));
    int m = n * 2 + 1;
    for(int i = 0; i < m; i++)
        tmp[i] = '#';
    for(int i = 0; i < n; i++)
        tmp[i * 2 + 1] = s[i + 1];
    int i = 0, j = 0;
    while(i < m) {
        while(i - j >= 0 and i + j < m and tmp[i - j] == tmp[i + j])
            j++;
        rad[i] = j;
        int k = 1;
        while(rad[i - k] < rad[i] - k) {
            rad[i + k] = rad[i - k];
            k++;
        }
        i += k;
        j = max(0, j - k);
    }
    for(int i = 1; i <= n; i++)
        go_odd[i] = rad[(i - 1) * 2 + 1] / 2;//abcba --> go_odd[3] = 3
    for(int i = 1; i <= n; i++)
        go_even[i - 1] = rad[(i - 1) * 2] / 2;//abccba --> go_even[3] = 3
}

void solveOdd(bool w) {
    int oth = 0;
    set < ii > go;
    for(int i = 1; i <= (n + 1) / 2; i++) {
        go.insert({go_odd[i], i});
    }
    for(int i = 1; i <= n; i++) {
        while(go.size()) {
            int x = go.rbegin() -> first;
            int id = go.rbegin() -> second;
            if(id < i) {
                go.erase(*go.rbegin());
                continue;
            }
            int mx = (id - i + 1) * 2 - 1;
            if(x > mx) {
                oth = max(oth, id);
                go.erase(*go.rbegin());
                continue;
            }
            break;
        }
        if(go.size())
            ans[w][i] = max(ans[w][i], go.rbegin() -> first);
        if(oth >= i)
            ans[w][i] = max(ans[w][i], (oth - i + 1) * 2 - 1);
        //printf("ans[%d] = %d oth = %d\n", i, ans[w][i]);
        int add = (n + 1) / 2 + i;
        go.insert({go_odd[add], add});
    }
}

int get(int x, int y) {
    y -= x - 1;
    return min(y, n - y) * 2;
}

void solveEven(bool w) {
    int oth = 0;
    set < ii > go;
    for(int i = 1; i <= (n + 1) / 2; i++) {
        go.insert({go_even[i], i});
    }
    for(int i = 1; i <= n; i++) {
        while(go.size()) {
            int x = go.rbegin() -> first;
            int id = go.rbegin() -> second;
            if(id < i) {
                go.erase(*go.rbegin());
                continue;
            }
            int mx = get(i, id);
            if(x > mx) {
                oth = max(oth, id);
                go.erase(*go.rbegin());
                continue;
            }
            break;
        }
        if(go.size())
            ans[w][i] = max(ans[w][i], go.rbegin() -> first);
        if(oth >= i)
            ans[w][i] = max(ans[w][i], get(i, oth));
        //printf("ans[%d] = %d\n", i, ans[w][i]);
        int add = (n + 1) / 2 + i;
        go.insert({go_even[add], add});
    }
}


int main () {
    
    scanf("%d %s", &n, s + 1);
    
    for(int i = 1; i <= n; i++)
        s[i + n] = s[i];
    
    ////////////////////////////////////
    
    n *= 2;
    manacher();
    n /= 2;
    
    for(int i = 1; i <= n + n; i++) {
        go_odd[i] *= 2;
        go_odd[i] -= 1;
        go_even[i] *= 2;
    }
    
    solveOdd(0);
    solveEven(0);
    
    ///////////////////////////////////
    
    reverse(s + 1, s + n * 2 + 1);
    
    n *= 2;
    manacher();
    n /= 2;
    
    for(int i = 1; i <= n + n; i++) {
        go_odd[i] *= 2;
        go_odd[i] -= 1;
        go_even[i] *= 2;
    }
    
    solveOdd(1);
    solveEven(1);
    
    ///////////////////////////////////
    
    printf("%d\n", max(ans[0][1], ans[1][1]));
    
    for(int i = 2; i <= n; i++) {
        printf("%d\n", max(ans[0][i], ans[1][n + 2 - i]));
    }
    
    return 0;
    
}








In    Java  :







import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class E2 {
    InputStream is;
    PrintWriter out;
    String INPUT = "";
    
    void solve()
    {
        int n = ni();
        char[] s = ns(n);
        char[] s2 = new char[2*n];
        for(int i = 0;i < n;i++){
            s2[i] = s2[i+n] = s[i];
        }
        int[] pal = palindrome(s2);
//        tr(pal, pal.length, n);
        long[] es = new long[16*n];
        int p = 0;
        for(int i = 0;i < 4*n;i+=2){
            pal[i] = Math.min(pal[i], n-((n&1)^1));
            es[p++] = (long)(i/2)<<32|i;
            es[p++] = (long)(i/2+pal[i]/2)<<32|i;
            es[p++] = (long)(i/2+n-pal[i]/2-1)<<32|i;
            es[p++] = (long)(i/2+n)<<32|i;
        }
        for(int i = 1;i < 4*n;i+=2){
            pal[i] = Math.min(pal[i], n-((n&1)));
            es[p++] = (long)(i/2)<<32|i;
            es[p++] = (long)(i/2+pal[i]/2)<<32|i;
            es[p++] = (long)(i/2+n-pal[i]/2)<<32|i;
            es[p++] = (long)(i/2+n)<<32|i;
        }
        
        Arrays.sort(es, 0, p);
        MaxHeap inc = new MaxHeap(4*n+1);
        MaxHeap dec = new MaxHeap(4*n+1);
        MaxHeap flat = new MaxHeap(4*n+1);
        
        int[] st = new int[4*n];
        int q = 0;
        for(int i = 0;i < 2*n-1;i++){
            while(q < p && es[q]>>>32 <= i){
                int ind = (int)es[q];
                if(st[ind] == 0){
                    inc.add(ind, (pal[ind]&1)-2*i);
                }else if(st[ind] == 1){
                    inc.remove(ind);
                    flat.add(ind, pal[ind]);
                }else if(st[ind] == 2){
                    flat.remove(ind);
                    dec.add(ind, pal[ind]+2*i);
                }else if(st[ind] == 3){
                    dec.remove(ind);
                }
                st[ind]++;
                q++;
            }
            if(i >= n-1){
//                tr("i", i);
                int max = 0;
                if(inc.size() > 0)max = Math.max(inc.max()+2*i, max);
//                tr(max);
                if(dec.size() > 0)max = Math.max(dec.max()-2*i, max);
//                tr(max);
                max = Math.max(flat.max(), max);
//                tr(max);
                out.println(max);
            }
        }
    }
    public static class MaxHeap {
        public int[] a;
        public int[] map;
        public int[] imap;
        public int n;
        public int pos;
        public static int INF = Integer.MIN_VALUE;
        
        public MaxHeap(int m)
        {
            n = m+2;
            a = new int[n];
            map = new int[n];
            imap = new int[n];
            Arrays.fill(a, INF);
            Arrays.fill(map, -1);
            Arrays.fill(imap, -1);
            pos = 1;
        }
        
        public int add(int ind, int x)
        {
            int ret = imap[ind];
            if(imap[ind] < 0){
                a[pos] = x; map[pos] = ind; imap[ind] = pos;
                pos++;
                up(pos-1);
            }
            return ret != -1 ? a[ret] : x;
        }
        
        public int update(int ind, int x)
        {
            int ret = imap[ind];
            if(imap[ind] < 0){
                a[pos] = x; map[pos] = ind; imap[ind] = pos;
                pos++;
                up(pos-1);
            }else{
                int o = a[ret];
                a[ret] = x;
                up(ret);
                down(ret);
//                if(a[ret] < o){
//                    up(ret);
//                }else{
//                    down(ret);
//                }
            }
            return x;
        }
        
        public int remove(int ind)
        {
            if(pos == 1)return INF;
            if(imap[ind] == -1)return INF;
            
            pos--;
            int rem = imap[ind];
            int ret = a[rem];
            map[rem] = map[pos];
            imap[map[pos]] = rem;
            imap[ind] = -1;
            a[rem] = a[pos];
            a[pos] = INF;
            map[pos] = -1;
            
            up(rem);
            down(rem);
            return ret;
        }
        
        public int max() { return a[1]; }
        public int argmax() { return map[1]; }
        public int size() {    return pos-1; }
        
        private void up(int cur)
        {
            for(int c = cur, p = c>>>1;p >= 1 && a[p] < a[c];c>>>=1, p>>>=1){
                int d = a[p]; a[p] = a[c]; a[c] = d;
                int e = imap[map[p]]; imap[map[p]] = imap[map[c]]; imap[map[c]] = e;
                e = map[p]; map[p] = map[c]; map[c] = e;
            }
        }
        
        private void down(int cur)
        {
            for(int c = cur;2*c < pos;){
                int b = a[2*c] > a[2*c+1] ? 2*c : 2*c+1;
                if(a[b] > a[c]){
                    int d = a[c]; a[c] = a[b]; a[b] = d;
                    int e = imap[map[c]]; imap[map[c]] = imap[map[b]]; imap[map[b]] = e;
                    e = map[c]; map[c] = map[b]; map[b] = e;
                    c = b;
                }else{
                    break;
                }
            }
        }
    }
    
    public static int[] palindrome(char[] str)
    {
        int n = str.length;
        int[] r = new int[2*n];
        int k = 0;
        for(int i = 0, j = 0;i < 2*n;i += k, j = Math.max(j-k, 0)){
            // normally
            while(i-j >= 0 && i+j+1 < 2*n && str[(i-j)/2] == str[(i+j+1)/2])j++;
            r[i] = j;
            
            // skip based on the theorem
            for(k = 1;i-k >= 0 && r[i]-k >= 0 && r[i-k] != r[i]-k;k++){
                r[i+k] = Math.min(r[i-k], r[i]-k);
            }
        }
        return r;
    }

    
    void run() throws Exception
    {

is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        out = new PrintWriter(System.out);
        
        long s = System.currentTimeMillis();
        solve();
        out.flush();
        if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
    }
    
    public static void main(String[] args) throws Exception { new E2().run(); }
    
    private byte[] inbuf = new byte[1024];
    private int lenbuf = 0, ptrbuf = 0;
    
    private int readByte()
    {
        if(lenbuf == -1)throw new InputMismatchException();
        if(ptrbuf >= lenbuf){
            ptrbuf = 0;
            try { lenbuf = is.read(inbuf); }
 catch (IOException e) { throw new InputMismatchException(); }
            if(lenbuf <= 0)return -1;
        }
        return inbuf[ptrbuf++];
    }
    
    private boolean isSpaceChar(int c) 
{ return !(c >= 33 && c <= 126); }
    private int skip()
{ int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
    
    private double nd() { return Double.parseDouble(ns()); }
    private char nc() { return (char)skip(); }
    
    private String ns()
    {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while(!(isSpaceChar(b)))
{ // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    
    private char[] ns(int n)
    {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while(p < n && !(isSpaceChar(b))){
            buf[p++] = (char)b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }
    
    private char[][] nm(int n, int m)
    {
        char[][] map = new char[n][];
        for(int i = 0;i < n;i++)map[i] = ns(m);
        return map;
    }
    
    private int[] na(int n)
    {
        int[] a = new int[n];
        for(int i = 0;i < n;i++)a[i] = ni();
        return a;
    }
    
    private int ni()
    {
        int num = 0, b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private long nl()
    {
        long num = 0;
        int b;
        boolean minus = false;

 while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private static void tr(Object... o) 
{ System.out.println(Arrays.deepToString(o)); }
}









In   C  :






#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void solve(char *str,int *a);
void init( int n );
void range_increment( int i, int j, int val );
int query( int i );
int max(int x,int y);
void update(int x,int y,int z);
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size);
char str[1000001]={0};
int N,NN,a[2000004],tree[2000000],ans[500000],b[500000],c[500000];

int main(){
  int i,j;
  scanf("%d%s",&NN,str);
  strncpy(str+NN,str,NN);
  solve(str,a);
  init(NN);
  for(i=0;i<4*NN;i++)
    if(a[i])
      if(i%2)
        update(i/2-a[i]/2,i/2+a[i]/2,a[i]);
      else
        update(i/2-a[i]/2,i/2+a[i]/2-1,a[i]);
  for(i=0;i<NN;i++){
    ans[i]=query(i);
    b[i]=ans[i];
    c[i]=i;
  }
  sort_a2(b,c,NN);
  for(i=NN;i>=0;i--){
    for(j=c[i];1;j=(j-1+NN)%NN)
      if(ans[j]-ans[(j-1+NN)%NN]>2)
        ans[(j-1+NN)%NN]=ans[j]-2;
      else
        break;
    for(j=c[i];1;j=(j+1)%NN)
      if(ans[j]-ans[(j+1)%NN]>2)
        ans[(j+1)%NN]=ans[j]-2;
      else
        break;
  }
  for(i=0;i<NN;i++)
    printf("%d\n",ans[i]);
  return 0;
}
void solve(char *str,int *a){
  char *p;
  int len,R,Ri,i,j,mi;
  len=strlen(str);
  p=(char*)malloc(2*(len+1)*sizeof(char));
  for(i=0;i<len;i++){
    p[2*i]='#';
    p[2*i+1]=str[i];
  }
  p[2*i]='#';
  p[2*i+1]=0;
  a[0]=R=Ri=0;
  for(i=1;i<=len*2;i++)
    if(i>=R){
      if(p[i]!='#')
        a[i]=1;
      else
        a[i]=0;
      for(j=i+1;1;j++)
        if(j<=2*len && 2*i-j>=0 && p[j]==p[2*i-j]){
          if(p[j]!='#')
            a[i]+=2;
        }
        else{
          Ri=i;
          R=j-1;
          break;
        }
    }
    else{
      mi=2*Ri-i;
      if(i+a[mi]>=R || mi==a[mi]){
        a[i]=R-i;
        for(j=R+1;1;j++)
          if(j<=2*len && 2*i-j>=0 && p[j]==p[2*i-j]){
            if(p[j]!='#')
              a[i]+=2;
          }
          else{
            Ri=i;
            R=j-1;
            break;
          }
      }
      else
        a[i]=a[mi];
    }
  free(p);
  return;
}
void init( int n ){
  N = 1;
  while( N < n ) N *= 2;
  int i;
  for( i = 1; i < N + n; i++ ) tree[i] = 0;
}
void range_increment( int i, int j, int val ){
  for( i += N, j += N; i <= j; i = ( i + 1 ) / 2, j = ( j - 1 ) / 2 )
  {
    if( i % 2 == 1 ) tree[i] = max(tree[i],val);
    if( j % 2 == 0 ) tree[j] = max(tree[j],val);
  }
}
int query( int i ){
  int ans = 0,j;
  for( j = i + N; j; j /= 2 ) ans = max(ans,tree[j]);
  return ans;
}
int max(int x,int y){
  return (x>y)?x:y;
}
void update(int x,int y,int z){
  if(z>NN){
    int m=x+z/2;
    if(z%2)
      if(NN%2)
        update(m-NN/2,m+NN/2,NN);
      else
        update(m-NN/2+1,m+NN/2-1,NN-1);
    else
      if(NN%2)
        update(m-NN/2,m+NN/2-1,NN-1);
      else
        update(m-NN/2,m+NN/2-1,NN);
  }
  if(y<NN){
    range_increment(0,x,z);
    range_increment(y+1,NN-1,z);
  }
  else
    range_increment(y-NN+1,x,z);
  return;
}
void sort_a2(int*a,int*b,int size){
  if (size < 2)
    return;
  int m = (size+1)/2,i;
  int*left_a,*left_b,*right_a,*right_b;
  left_a=(int*)malloc(m*sizeof(int));
  right_a=(int*)malloc((size-m)*sizeof(int));
  left_b=(int*)malloc(m*sizeof(int));
  right_b=(int*)malloc((size-m)*sizeof(int));
  for(i=0;i<m;i++){
    left_a[i]=a[i];
    left_b[i]=b[i];
  }
  for(i=0;i<size-m;i++){
    right_a[i]=a[i+m];
    right_b[i]=b[i+m];
  }
  sort_a2(left_a,left_b,m);
  sort_a2(right_a,right_b,size-m);
  merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
  free(left_a);
  free(right_a);
  free(left_b);
  free(right_b);
  return;
}
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size){
  int i = 0, j = 0;
  while (i < left_size|| j < right_size) {
    if (i == left_size) {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      j++;
    } else if (j == right_size) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      i++;
    } else if (left_a[i] <= right_a[j]) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      i++;
    } else {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      j++;
    }
  }
  return;
}








View More Similar Problems

Delete a Node

Delete the node at a given position in a linked list and return a reference to the head node. The head is at position 0. The list may be empty after you delete the node. In that case, return a null value. Example: list=0->1->2->3 position=2 After removing the node at position 2, list'= 0->1->-3. Function Description: Complete the deleteNode function in the editor below. deleteNo

View Solution →

Print in Reverse

Given a pointer to the head of a singly-linked list, print each data value from the reversed list. If the given list is empty, do not print anything. Example head* refers to the linked list with data values 1->2->3->Null Print the following: 3 2 1 Function Description: Complete the reversePrint function in the editor below. reversePrint has the following parameters: Sing

View Solution →

Reverse a linked list

Given the pointer to the head node of a linked list, change the next pointers of the nodes so that their order is reversed. The head pointer given may be null meaning that the initial list is empty. Example: head references the list 1->2->3->Null. Manipulate the next pointers of each node in place and return head, now referencing the head of the list 3->2->1->Null. Function Descriptio

View Solution →

Compare two linked lists

You’re given the pointer to the head nodes of two linked lists. Compare the data in the nodes of the linked lists to check if they are equal. If all data attributes are equal and the lists are the same length, return 1. Otherwise, return 0. Example: list1=1->2->3->Null list2=1->2->3->4->Null The two lists have equal data attributes for the first 3 nodes. list2 is longer, though, so the lis

View Solution →

Merge two sorted linked lists

This challenge is part of a tutorial track by MyCodeSchool Given pointers to the heads of two sorted linked lists, merge them into a single, sorted linked list. Either head pointer may be null meaning that the corresponding list is empty. Example headA refers to 1 -> 3 -> 7 -> NULL headB refers to 1 -> 2 -> NULL The new list is 1 -> 1 -> 2 -> 3 -> 7 -> NULL. Function Description C

View Solution →

Get Node Value

This challenge is part of a tutorial track by MyCodeSchool Given a pointer to the head of a linked list and a specific position, determine the data value at that position. Count backwards from the tail node. The tail is at postion 0, its parent is at 1 and so on. Example head refers to 3 -> 2 -> 1 -> 0 -> NULL positionFromTail = 2 Each of the data values matches its distance from the t

View Solution →