In this HackerRank Circular Palindromes problem solution we have 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.
Problem solution in Python.
#!/bin/python3
import os
import sys
import random
import bisect
#
# Complete the circularPalindromes function below.
#
def get_len(s, ll, flag):
# use flag = 0 for odd number of letters in palindrome, 1 for even
maxlen = 1
l1 = ll - 2
l2 = ll + 1 + flag
while l1>=0 and l2 < len(s) and s[l1] == s[l2]:
maxlen += 1
l1 -= 1
l2 += 1
return 2*maxlen + flag
def max_pal(s):
# find the length of the longest palindrome in s
ls = len(s)
maxlen = 1
for ll in range(1, ls):
if s[ll-1] == s[ll]:
newlen = get_len(s, ll, 0)
if newlen > maxlen:
maxlen = newlen
for ll in range(1, ls-1):
if s[ll-1] == s[ll+1]:
newlen = get_len(s, ll, 1)
if newlen > maxlen:
maxlen = newlen
return maxlen
def get_len_round_fast(slist, ll, lens):
ls = len(slist)
if ls == 1:
return (slist[0][1], slist[0][2])
start = slist[ll][1]
end = slist[ll][2]
l1 = ll - 1
l2 = ll + 1
notdone = True
while notdone and (end - start)<lens and slist[l1 % ls][0] == slist[l2 % ls][0]:
lgth1 = slist[l1][2]-slist[l1][1]
if lgth1 < 0:
lgth1 += lens
ls2 = l2 % ls
lgth2 = slist[ls2][2]-slist[ls2][1]
if lgth2 < 0:
lgth2 += lens
lmax = lens - (end-start)
if lgth1 != lgth2:
notdone = False
# make lgth2 the smaller for subsequent calculations
if lgth1 < lgth2:
lgth2 = lgth1
if lgth2 + lgth2 > lmax:
lgth2 = lmax//2
notdone = False
end+= lgth2
start -= lgth2
l1 -= 1
l2 += 1
# print(l1, l2)
return (start, end)
def compress_string(s):
# replaces strings of contiguous identical characters with (char, #) pairs
# where # is the end of the string sequence
ls = []
cc = '.'
start = 0
for ss in range(len(s)):
if s[ss] != cc: # new char
ls.append((cc, start, ss))
start = ss
cc = s[ss]
ls.append((cc, start, len(s))) # append the last characters encountered
ls.pop(0) # first value is a throwaway one
if ls[0][0] == ls[-1][0]: # stitch the ends, move the start of sequence before 0
ls[0] = (ls[0][0], ls[-1][1]-len(s), ls[0][2])
ls.pop() # remove last element, now that it is combined with the first
return ls
def make_pal_dict(slist, lens):
ls = len(slist)
dict1 = {}
list1 = []
for ll in range(ls):
(start, stop) = get_len_round_fast(slist, ll, lens)
# print(ll, start, stop)
lgth = stop - start
if lgth > 1:
if start < 0:
start, stop = start+lens, stop+lens
if lgth in dict1:
dict1[lgth].append((start, stop))
else:
dict1[lgth]= [(start, stop)]
bisect.insort(list1, lgth)
for (_, start, stop) in slist:
lgth = stop - start
if lgth > 1:
if start < 0:
start, stop = start+lens, stop+lens
if lgth in dict1:
if (start, stop) in dict1[lgth]:
dict1[lgth].remove((start, stop))
dict1[lgth].append((-start, -stop))
else:
dict1[lgth]= [(-start, -stop)]
bisect.insort(list1, lgth)
return (dict1, list1)
def cp(s):
ls = len(s)
slist = compress_string(s)
# print(slist)
(dict1, list1) = make_pal_dict(slist, ls)
# print(dict1, list1)
maxes = [] # value for k = 0
ll = len(list1)-1 # start here to look for longest palindrome
for k in range(ls):
maxlgth = 1
done = False
ks = k + ls
for ind in range(ll, -1, -1): # go backwards through list of lengths
if done: # max value already reached for a longer word
break
lgth = list1[ind]
if lgth < maxlgth: # only shorter words available past here
break
for (start, stop) in dict1[lgth]:
if start<=0 and stop <= 0: # same chars, no need to cut palindrome at both ends
# print(start, stop, k)
if -start <= k < -stop:
lgth1 = max(-stop - k, k+start)
else:
lgth1 = lgth
if -start < ks <= -stop:
lgth2 = max(ks + start, -stop - ks)
else:
lgth2 = lgth
#print(lgth1, lgth2)
else:
# print(lgth, maxlgth, k, start, stop)
if start <= k <= stop:
lgth1 = abs(start+stop-k-k)
else:
lgth1 = lgth
if start <= ks <= stop:
lgth2 = abs(start+stop-ks-ks)
else:
lgth2 = lgth
if lgth1 > lgth2:
lgth1 = lgth2
if maxlgth < lgth1:
maxlgth = lgth1
# print(maxlgth)
if lgth1 == lgth:
done = True
break
# print("k=", k, "ml=", maxlgth)
maxes.append(maxlgth)
return maxes
def circularPalindromes(s):
#
# Write your code here.
#
debug = 0
if debug == 0:
return cp(s)
elif debug == 1:
for ii in range(1000):
s = ""
for jj in range(10):
s += chr(97 + random.randrange(0, 26))
r1 = cp(s)
r = cp_gold(s)
if r1 != r:
print(r1, "should be", r, "for", s)
return [1, 1, 1]
elif debug == 2:
return cp_gold(s)
else:
(dict1, list1) = make_pal_list(s)
print(dict1, list1)
return cp_gold(s)
def rotate_s(s, val):
val = val % len(s)
return s[val:]+s[:val]
def cp_gold(s):
#
# Write your code here.
#
ls = len(s)
maxes = [max_pal(s)]
for ll in range(1, ls):
s = rotate_s(s, 1)
maxes.append(max_pal(s))
return maxes
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
n = int(input())
s = input()
result = circularPalindromes(s)
fptr.write('\n'.join(map(str, result)))
fptr.write('\n')
fptr.close()
Problem solution 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)); }
}
Problem solution in C++.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
using namespace std;
const int MAXN = 5e5, MAXX = MAXN << 1, MAXLEAVES = 1 << 19;
char S[MAXX + 1]; int R[2][MAXX + 1], fsize, T[2][MAXX + 1];
void manacher(const int length, const int rx) {
register int i, j, k; int *table = R[rx];
for (i = j = 0; i < length; i += k, j = max(j - k, 0)) {
while (i - j >= 0 && i + j + rx < length && S[i - j] == S[i + j + rx])
++j;
table[i] = j;
for (k = 1; k < j && table[i - k] != table[i] - k; ++k) {
table[i + k] = min(table[i - k], table[i] - k);
}
}
}
int tree[(MAXLEAVES << 1) + 1], rval, ileft, iright, leaves;
void update_tree(const int x, const int left, const int right) {
if (ileft > right || iright < left) { return; } if (ileft <= left && right <= iright) {
//node completely inside the update interval
tree[x] = max(tree[x], rval);
} else {
int mid = (left + right) >> 1;
update_tree(x << 1, left, mid);
update_tree((x << 1) + 1, mid + 1, right);
}
}
void adjust_and_gather(const int pos, const int parity) {
int &ptr = R[parity][pos];
int diff = (ptr << 1) - (!parity) - fsize, lx, rx, flen;
if (diff > 0) {
diff += (diff & 1);
ptr -= diff >> 1;
}
lx = pos - ptr + 1;
rx = pos + ptr - (parity == 0); flen = (ptr << 1) - (!parity);
if ((parity == 0 && ptr > 1) || (parity == 1 && ptr > 0)) {
T[0][lx] = max(T[0][lx], flen); T[1][rx] = max(T[1][rx], flen);
ileft = max(0, rx - fsize + 1), iright = min(fsize - 1, lx);
rval = flen;
update_tree(1, 0, leaves - 1);
}
}
inline void process_manacher_table(const int length) {
for (register int i = 0; i < length; ++i) {
adjust_and_gather(i, 0); //odd length;
adjust_and_gather(i, 1); //even length;
}
}
inline int read_tree(const int pos) {
register int x = pos + leaves;
int result = 1;
while (x) {
result = max(result, tree[x]);
x >>= 1;
}
return result;
}
inline void init_leaves(const int n) {
leaves = 1; while (leaves < n)
{
leaves <<= 1;
}
}
int main() {
register int N, i, answer;
scanf("%d%s", &N, S);
memcpy(S + N, S, (N - 1) * sizeof(char));
init_leaves(N);
fsize = N, N = (N << 1) - 1;
manacher(N, 0); //odd length;
manacher(N, 1); //even length;
process_manacher_table(N);
for (i = 1; i < N; ++i) {
T[0][i] = max(T[0][i], T[0][i - 1] - 2);
T[1][N - i - 1] = max(T[1][N - i - 1], T[1][N - i] - 2);
}
for (i = 0; i < fsize; ++i) {
answer = read_tree(i);
answer = max(answer, T[0][i]);
answer = max(answer, T[1][i + fsize - 1]);
printf("%d\n", answer);
}
return 0;
}Problem solution 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;
}
0 Comments