2015
04-13

# Palindrome

Given a string S,you are asked to find the longest palindrome in the substring [l,r].

The first line is a number T which indicates the number of test cases

then follows a string s(length(s)<200000)
s can consists all ascii characters
Then an integer q,q querys(q<200000)
each query is two integer l,r.
find the longest palindrome in the substring [l,r].

The first line is a number T which indicates the number of test cases

then follows a string s(length(s)<200000)
s can consists all ascii characters
Then an integer q,q querys(q<200000)
each query is two integer l,r.
find the longest palindrome in the substring [l,r].

1
aaabbcc
5
1 7
1 4
2 3
4 5
2 5

3
3
2
2
2

Hint1 7 means aaabbcc the longest palindrome substring is aaa,whose length is 3.
4 5 means bb the longest palindrome substring is bb,whose length is 2. 

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

using namespace std;

const int MAXN = 222222;

char str[ MAXN ];
int data[ MAXN * 2 ];
int p[ MAXN * 2 ];
int d[ MAXN * 2 ][30];
int n, len;

void init()
{
int id,MaxL,MaxId;
int i;
MaxL=MaxId=0;
len = strlen(&str[1]);
for (i=1; i <= len; i++)
{
data[(i<<1)]=str[i];
data[(i<<1)+1]=2;
}
data[0]=1;
data[1]=2;
n=(i<<1)+2;
data[n]=0;
MaxId=MaxL=0;
p[0] = 1;
for (i=1; i<n; i++)
{
if (MaxId>i)
p[i]=min(p[2*id-i],MaxId-i);
else
p[i]=1;
while (data[i+p[i]] == data[i-p[i]])
p[i]++;
if (p[i]+i>MaxId)
MaxId=p[i]+i,id=i;
//printf( "p[%d]=%d\n", i, p[i] );
}
for ( i = 1; i < n; ++i ) --p[i];

return;
}

void RMQinit()
{
for ( int i = 0; i <= n; ++i ) d[i][0] = p[i];
for ( int j = 1; ( 1 << j ) <= n; ++j )
for ( int i = 1; i + j - 1 <= n; ++i )
d[i][j] = max( d[i][j - 1], d[ i + (1<<(j-1))][j - 1] );
return;
}

int RMQquery( int L, int R )
{
int k = 0;
while ( (1 << (k + 1)) <= R - L + 1 ) ++k;
return max( d[L][k], d[ R - ( 1 << k ) + 1 ][k] );
}

bool check( int L, int R, int mid )
{
//if ( L + mid > R - mid ) return false;
int ans = RMQquery( L + mid, R - mid );
//printf("[%d %d]:%d\n", L + mid, R - mid, ans );
//printf("ans = %d, mid = %d\n", ans, mid );
if ( ans >= mid )
{
//puts("****");
return true;
}
return false;
}

int BiSearch( int l, int r, int L, int R )
{
int ans = 1;
while ( l <= r )
{
int mid = ( l + r ) >> 1;
if ( check( L, R, mid ) )
{
l = mid + 1;
ans = mid;
}
else r = mid - 1;
}
return ans;
}

int main()
{
int T;
scanf( "%d", &T );
getchar();
while ( T-- )
{
memset( d, 0, sizeof(d) );
memset( p, 0, sizeof(p) );
gets( &str[1] );
init();
RMQinit();

int Q;
scanf( "%d", &Q );
while ( Q-- )
{
int a, b;
scanf( "%d%d", &a, &b );
if ( a < 1 ) a = 1;
if ( b > len ) b = len;
if ( a > len )
{
puts("0");
continue;
}
if ( a > b ) swap( a, b );
int ans = BiSearch( 1, b - a + 1, a*2 - 1, b*2 + 1 );
printf( "%d\n", ans );
}
getchar();
}
return 0;
}

1. Pingback: Lil Wayne

2. Pingback: singer

3. Pingback: فروش دوربین های مدار بسته مخفی

4. Pingback: نصب و اجرای دوربین مداربسته

5. Pingback: ترمیم مو و کاشت مو

6. Pingback: sex toys for beginner

7. Pingback: طراحی سایت فروشگاه

8. Pingback: penis ring

9. Pingback: نصب دوربین های مدار بسته

10. Pingback: double penetration

11. Pingback: black polythene sheeting

12. Pingback: Magnetic

13. Pingback: خرید اپل ایدی با ایمیل شخصی

14. Pingback: sex gel

15. Pingback: کفسابی در تهران

16. Pingback: وکیل

17. Pingback: eve's strap- on play set

18. Pingback: vibrator

19. Pingback: poker sex

20. Pingback: personal massager

21. Pingback: penile toy

22. Pingback: Amber Hawkins

23. Pingback: driving tips

26. Pingback: Nipple Toys

27. Pingback: Anal toys

28. Pingback: آموزش نصب دوربین مدار بسته

29. Pingback: phildot

30. Pingback: bondage toys

31. Pingback: vibrator pleasure

32. Pingback: Butt plugs

33. Pingback: Dildo

34. Pingback: accounting

35. Pingback: rabbit sex toy

36. Pingback: anal sex toys

37. Pingback: آموزش نصب دوربین مدار بسته

38. Pingback: Middleweight uniform separates

39. Pingback: benefits of watching porn

40. Pingback: php ecommerce

42. Pingback: auction marketplace

43. Pingback: authentic serial keys

44. Pingback: Miami

47. Pingback: Blend City 42

48. Pingback: flexible tile adhesive supplier

49. Pingback: Hanoi Tam Coc

50. Pingback: ノロウイルス

51. Pingback: revize jerabu

52. Pingback: airfreight

55. Pingback: http://tarmimemoo.net

56. Pingback: massage prostate

57. Pingback: urgent care glendale

58. Pingback: ترمیم مو بیماران

59. Pingback: best sex lube

60. Pingback: dp sex toy

61. Pingback: rechargeable bullet vibrator

62. Pingback: toys for couples

63. Pingback: big vibrator

64. Pingback: تردمیل

65. Pingback: the bullet sex toy

66. Pingback: lgbt sex toys

67. Pingback: خرید انی apple id

68. Pingback: اجاره ویلا یک روزه در کردان

69. Pingback: suction cup dildo

70. Pingback: best vibrating cock ring

72. Pingback: خرید اپل ایدی با ایمیل شخصی

73. Pingback: magnetic paper

74. Pingback: خرید آنلاین تردمیل خانگی

75. Pingback: worktop protection

76. Pingback: anti slip tape

77. Pingback: flame retardant polythene

78. Pingback: sasha grey pocket pal

79. Pingback: massager wand

80. Pingback: bdsm

81. Pingback: best ben wa balls

82. Pingback: sex diary

83. Pingback: bondage handcuffs

84. Pingback: خرید اپل ایدی

85. Pingback: php open source

86. Pingback: How to give a woman oral sex

87. Pingback: lgbt anal toys

88. Pingback: bullet sex toy

89. Pingback: bullet egg vibrator

91. Pingback: vpn خرید پرسرعت

92. Pingback: japanese manga

93. Pingback: Steel leg stretching machine

94. Pingback: adam \u0026 eve clit sensitizer

95. Pingback: gay sex toys

96. Pingback: ترمیم مو

97. Pingback: naughty nurse

98. Pingback: تعمیر لوازم خانگی

99. Pingback: vibrator for her

100. Pingback: tratamento de Dependência Química

101. Pingback: Minikert

102. Pingback: Masturbator

103. Pingback: web site

105. Pingback: the bullet vibe

106. Pingback: Consulting

107. Pingback: PHIL

108. Pingback: Best Ben Wa Balls

109. Pingback: Sex Toy for Men

110. Pingback: lifelike dildo

112. Pingback: g spot

113. Pingback: womens luxe vibe

115. Pingback: rechargeable sex toy

116. Pingback: sex toys for beginners

117. Pingback: probiotic sauerkraut kvass

118. Pingback: pc games for windows 10

121. Pingback: butt plug beginner

122. Pingback: lingerie chemise

123. Pingback: different type of vibrator

124. Pingback: Macho Stallion Erection Keeper

126. Pingback: pipedream sex toys

127. Pingback: A\u0026E beginner's power pump

128. Pingback: Penis Pump Video

129. Pingback: Best Vibrating Cock Ring

130. Pingback: vibrator

131. Pingback: let's talk about sex

132. Pingback: oral

133. Pingback: jbeatz

134. Pingback: adam and eve sex toy shop

135. Pingback: best vibrator