## 11888 - Abnormal 89's

Moderator: Board moderators

bm_anas
New poster
Posts: 10
Joined: Fri May 15, 2009 9:13 pm

### 11888 - Abnormal 89's

Any idea how to solve this problem??

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

### Re: 11888 - Abnormal 89's

FOR k : 1...n
make 2 strings 1..k and k+1... n ... now a simple check ...
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### Re: 11888 - Abnormal 89's

I haven't solved this problem yet, but isn't your approach n^2 and won't it get TLE?

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

### Re: 11888 - Abnormal 89's

I got AC in 0.088 with this Trivail solution ...
But i think there is also another solution ..
if the string is s ... and its reverse is r....
try to find r in s+s ..... if you use strstr() maybe you will Timeout ... )
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

### Re: 11888 - Abnormal 89's

Angeh wrote:I got AC in 0.088 with this Trivail solution ...
But i think there is also another solution ..
if the string is s ... and its reverse is r....
try to find r in s+s ..... if you use strstr() maybe you will Timeout ... )
I was about to implement O(N) solution. With proper tests your solution would definitely TLE.

Mizanur Rahman(IUK)
New poster
Posts: 12
Joined: Wed Aug 18, 2010 12:07 pm

### Re: 11888 - Abnormal 89's

Code: Select all

``````#include<stdio.h>
#include<string.h>

int pal(char a[])
{
char b={' '};
//strcpy(b,a);
long int n=strlen(a),i;
//strrev(b);
for(i=0;i<n;i++)
b[i]=a[n-i-1];
if(strcmp(a,b)==0)
return 1;
return 0;
}
int al(char a[])
{
long int n=strlen(a);
long int i,k;
for(i=0;i<n-1;i++)
{
long int j;k=0;
char b={' '},c={' '};
strncpy(b,a,i+1);
if(pal(b))
{
for(j=i+1;j<n;j++)
{c[k]=a[j];k++;}
if(pal(c)) return 1;
}
}
return 0;
}
int main()
{
int n,i;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
char a;
scanf("%s",a);
if(al(a))
printf("alindrome\n");
else if(pal(a))
printf("palindrome\n");
else printf("simple\n");
}
return 0;
}
``````

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

### Re: 11888 - Abnormal 89's

Mizanur, on each iteration when looking for alindrome the algorithm copies whole string. Try to find a way not to copy the string and I believe it should be AC.

patsp
New poster
Posts: 12
Joined: Tue Sep 21, 2010 8:51 pm

### Re: 11888 - Abnormal 89's

How to solve this problem in O(N) ??

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

### Re: 11888 - Abnormal 89's

if the string is s ... and its reverse is r....
try to find r in s+s
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

robot
New poster
Posts: 29
Joined: Sun May 24, 2009 8:39 pm

### Re: 11888 - Abnormal 89's

Hi anas
if You solve this problem O(n) , you have to try using KMP(only just Prefix function)

ASU(SUST) Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

### Re: 11888 - Abnormal 89's

I am using HASHING TO find if S[L.. R] is a palindrome or not ?

Code: Select all

``````#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */
#define LMT				200005
#define ll				long long
#define ull				unsigned long long
#define mod				1000000007
#define MEMSET_INF		63
#define MEM_VAL			1061109567
#define FOR(i,n)			for( int i=0 ; i < n ; i++ )
#define mp(i,j)			make_pair(i,j)
#define lop(i,a,b)		for( int i = (a) ; i < (b) ; i++)
#define pb(a)			push_back((a))
#define gc				getchar_unlocked
#define PI				acos(-1.0)
#define inf				1<<30
#define lc				((n)<<1)
#define rc				((n)<<1 |1)
#define msg(x)			cout<<x<<endl;

/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
inline void sc(int &x)
{
register int c = gc();
x = 0;
int neg = 0;
for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}

template <class T> inline T bigmod(T p,T e,T M){
ull ret = 1;
for(; e > 0; e >>= 1){
if(e & 1) ret = (ret * p) % M;
p = (p * p) % M;
} return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

/*************************** END OF TEMPLATE ****************************/

char P[LMT] , RP[LMT];
ull H [LMT];
ull RH[LMT];
ull base = 117;
const ull MOD =1000000007ULL;
ull kPower[LMT];

ull getHash (int L,int R,ull HASH[])
{
ull kp =( MOD +  HASH[R] - (L>0 ? HASH[L-1] : 0)) % MOD ;
kp =( kp * modinverse(kPower[L], MOD)) % MOD;
return kp;
}
int main()
{

int tc ;
scanf("%d",&tc);
ull t = 1;
for(int i = 0 ; i < LMT ; i ++ ) {
kPower[i] = t % MOD;
t = (t * base ) % MOD ;
}
while (tc -- ) {
scanf("%s", P );
int len = (int) strlen(P);
strcpy(RP , P);
reverse(RP, RP + len);

ull hash = 0 ;
for (int i = 0 ; i < len ; i ++ ) {
H[i] = hash + kPower[i]*( P[i] -'a' +1 );
H[i] %= MOD;
hash = H[i];
}
hash = 0;
for (int i = 0 ; i < len ; i ++ ) {
RH[i] = hash + kPower[i]*( RP[i] -'a' + 1);
RH[i] %= MOD;
hash = RH[i];
}

int isp = 0;
if(RH[len-1] == H[len-1]) isp = 1;

for (int k = 0 ; k < len - 1  ; k ++ ) {
ull fh = getHash(0,k,H);
ull rfh = getHash(len - 1 - k , len-1 , RH );

ull lf = getHash(k+1, len-1 , H);
ull rlf = getHash(0, len - 1 - k - 1, RH );
if (fh == rfh && lf == rlf ) {
isp =2;
break;
}
}

if(isp >= 2) printf("alindrome\n");
else if (isp == 1 ) printf("palindrome\n");
else printf("simple\n");

}
return 0;
}

``````

Mukit Chowdhury
Learning poster
Posts: 99
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

### Re: 11888 - Abnormal 89's

A little bit confused !!! Though I've got AC, but I'm not sure, if my solution should get this verdict. I have tried with each index so that by this index, I can make two palindrome from 0 to index and index+1 to len-1. If I can make two palindrome, then given input is alindrome, otherwise not. If the input string length is 200000 and first half of that string is a palindrome and second half of that string is not a palindrome, then my case should get TLE. Shouldn't that?