257 - Palinwords

[Revenger]

I can't understand why my program get Runtime Error on 17 second. I tested it on many tests but with no result. Can anyone help me? Please!

[pascal]Program p257;

Const LSet = ['A'..'Z'];

Var S : String;
Ch : Char;

Function IsPalindrome(S : String) : Boolean;
Var i,len : integer;
begin
IsPalindrome:=False;
len:=length(S);
for i:=1 to len do
if S<>S[len-i+1] then exit;
IsPalindrome:=True;
end;

Function Check(S1,S2 : String) : Boolean;
Var Smin,Smax : String;
begin
if length(S1)<length(S2) then begin
Smin:=S1;
Smax:=S2;
end else begin
Smin:=S2;
Smax:=S1;
end;
Check:=Not((Smax=Smin)or(Pos(Smin,Smax)>0));
end;

Function IsPalinword(S : String) : Boolean;
Var i,ie,l : Integer;
S1,SArr : String;
begin
IsPalinword:=True;
l:=length(S);
SArr:='';
for i:=1 to l-2 do
for ie:=i+2 to l do begin
S1:=Copy(S,i,ie-i+1);
if IsPalindrome(S1) then begin
if SArr='' then SArr:=S1 else
if Check(S1,SArr) then exit;
end;
end;
IsPalinword:=False;
end;

begin
S:='';
While Not Eof(InPut) Do begin
Read(Ch);
if Ch in LSet then
S:=S+Ch
else begin
if S<>'' then if IsPalinword(S) then Writeln(S);
S:='';
end;
end;
if S<>'' then if IsPalinword(S) then Writeln(S);
end.[/pascal]

[xenon]

I don't know why, but you get an 'Invalid memory reference' when you use S:=S+Ch and S gets too long. I'm not sure where the limit lies, but it's below the standard stringlength of 255. Using a longer stringtype (1000 f.i.) doesn't help; the thing still crashes below 255.
I guess it's a bug in GNU Pascal. My compiler lives with it allright.
Find another way to put the word into a string

P.S. My guess is you will get a TLE now, because the algorithm is too slow. It's not your fault, in principle, but the GNU compiler throws in a lot of range-checking, which makes string-operations particularly slow . You might be lucky though. My program finished in just under 30 seconds.

[xenon]

Just looked it up in the GNU-Pascal buglist, and it appears to be a known bug. Every time you use the string-concatenator '+', the local stack gets increased by 16 bytes (the operator assigns them, but never releases them). Although the stack is rather big (something like a meg, or so) it gets filled sometimes, because the operataor is used for every single letter in the input, and then causes the error.
You can avoid it by using your own procedure stringadd:
[pascal]procedure stringadd(var s:string;c:char);
begin s:=s+c; end;[/pascal]
because then the local stack gets cleared on every function return. (But it makes your program slower).

[Revenger]

In problem is written

each line in the input file contains at most 255 characters in all

So I think that it's not a error in my program, but i try to do my program another way.

[Revenger]

You are rigth. I changed my program and get TLE. Can you give me a hint to your algorithm?

[xenon]

Just got your program accepted (it ran for 27 seconds), after 'shaving off' some string-copies:
[pascal]
Program p257;
(* source code deleted *)
[/pascal]
Use strings as var in function calls, if possible, and avoid using local strings, if time is critical.
Since this is a working solution to this problem, i'll delete it after you read it. please reply!

[Revenger]

Thank you very much! I get Accepted!

[passwd]

hi,

I'm trying to solve problem 257(paliwords) but I got time limit ,
I confirmed the code a lot of times and I don't know where is
the problem ...

[c]

Code: Select all

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

/*#define DEBUG*/

typedef struct cel {
  struct cel* prox;
  char word[257];
} Lista;
typedef Lista* lista;

lista listInsert(lista l,char* str) {
  lista novo = (lista) malloc(sizeof(Lista));
  if(!novo) { printf("erro ao alocar no !!\n"); exit(1); }
  novo->prox=l;
  strcpy(&novo->word[0],str);
  l=novo;
  return l;
}

lista listSearch(lista l,char *str) {
  lista aux=l;
  int i=0,j=0;
  i=strlen(str);
  while(aux!=NULL) {
    j=strlen(aux->word);
    if(i==j) { if(strcmp(str,&aux->word[0])==0) return aux; }
    else if(i>j) { if(strstr(str,&aux->word[0])!=NULL) return aux; }
    else { if(strstr(&aux->word[0],str)!=NULL) return aux; }
    aux=aux->prox;
  }
  return NULL;
}

int listItens(lista l) {
  lista aux=l;
  int num=0;
  while(l!=NULL) {
    l=l->prox;
    ++num;
  }
  return num;
}

#ifdef DEBUG
  void listPrint(lista l) {
    lista p=l;
    printf("\n----\n");
    while(p!=NULL) {
      printf("%s\n",p->word);
      p=p->prox;
    }
    printf("----\n");
  }
#endif

int palindrome(char palin[]) {
  int i=0,j,k,tam=strlen(palin);
  --tam;
  k=tam/2;
  for(i=0,j=tam;i<=k;++i) {
    if(i==j) break;
    if(palin[i]!=palin[j]) {
      #ifdef DEBUG
        printf("palindrome: tam: %d , str: %s  ,  nao\n",tam,palin);
      #endif
      return 1;
    }
    --j;
  }
  #ifdef DEBUG
    printf("palindrome: tam: %d , str: %s  ,  sim\n",tam,palin);
  #endif
  return 0;
}


int main() {
  
  char linha[257];

  while(scanf("%s",linha)!=-1) {
      lista l=NULL;
      int i,j=strlen(linha),k,m,p;
      if( (j==0) || (j==1) || (j==2) ) continue;
	  #ifdef DEBUG
		  printf("%s -- %d -- %d\n",linha,strlen(linha),palindrome(linha));
	  #endif
      m=j-2;
      for(i=0;i<m;i++) {
         for(k=i+2;k<j;k++) {
           char aux[257];
           memcpy(&aux[0],&linha[i],k+1);
           aux[k-i+1]='\0';
		   if(palindrome(aux)==0) {
             if(strlen(aux)!=j) if(listSearch(l,&aux[0])==NULL) l=listInsert(l,&aux[0]);
           }
         }
      }
      #ifdef DEBUG
        listPrint(l);
      #endif
      if(listItens(l)>1) printf("%s\n",linha);
  }
  return 0;
}

[/c]

[kenneth]

Hi

Would anyone be able to help me out on this? I have got the following error message with the online judge but not on my own computer.

Thanks

Code: Select all

#define REP(i, n) for (int i = 0; i < (n); i++)
#define FOREACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); i++)

bool palinword(string word)
{
    set <string> p;

    REP(i, word.size() - 2)
    {
        for (int j = 3; j <= word.size() - i; j++)
            if (palindrome(word.substr(i, j)))
                p.insert(word.substr(i, j));
    }

    FOREACH(i, p)
    {
        for (set <string>::iterator j = i; j != p.end(); j++)
            if (((*i).find(*j) == -1) && ((*j).find(*i) == -1))
                 return true;
    }

    return false;
}

[jiarung.yeh]

I don't know what I wrong

I only check the substring's length is 3 ans 4.

Code: Select all

#include <iostream>
#include <cstring> 
#include <string>
#include <vector>
#include <algorithm>

using std::find ;
using std::vector ;
using std::string ;
using std::cin ;
using std::cout ;
using std::endl ;

bool is_palin( string ) ;
bool is_aph( char ) ;

int main(){
	string s ;
	char line[300] ;
	int i , j , li ;
	while( cin.getline( line , 300 ) ){
		li = 0 ;
		while( true ){
			//   find s to check is a palinword
			s = "" ;
			while( true ){
				if( is_aph( line[li] ) || li == strlen( line ) )
					break ;
				++ li ;
			}
			if( li == strlen( line ) )
				break ;
			for( ; is_aph( line[li] ) ; ++ li )
				s += line[li] ;

			// check is a palinword
			vector<string>palin( 0 ) ;
			bool get_ans = false ;
			for( i = 0 ; !get_ans && i < s.length() ; ++ i ){
				for( j = 3 ; j <= s.length() - i && j <= 4 ; ++ j ){
					string s_temp = s.substr( i , j ) ;
					if( !is_palin( s_temp )  || 
									palin.end() != find( palin.begin() , palin.end() , s_temp ) )
						continue ;
					else
						palin.push_back( s_temp ) ;

					if( palin.size() == 2 )
						get_ans = true ;
				}
			}

			if( get_ans )
				cout << s << endl ;

			for( std::vector<string>::iterator I = palin.begin() ; I != palin.end() ; ++ I )
				cout << *I << " " ;
			cout << endl ; 
		}
	}
}

bool is_palin( string s1 ){
	for( int i = 0 , j = s1.length() - 1 ; i < s1.length() / 2 ; -- j , ++ i )
		if( s1[i] != s1[j] )
			return false ;
	return true ;
}

bool is_aph( char ch ){
	if( ( ch <= 'z' && ch >= 'a' ) || ( ch <= 'Z' && ch >= 'A' ) )
		return true ;
	return false ;
}

[Jan]

Checking only length 3 and 4 is not sufficient. I haven't solved it yet but I can give you some examples.

Input:

Code: Select all

ABCBAPBCBP

Output:

Code: Select all

ABCBAPBCBP

You have to copy a word if it contains at least two different palindromes and one should not contain the other one.

In the above example if you check for palindromes of length 3 or 4, your code will find 'BCB'. So, according to your algorithm its not a palinword.

But its a palinword because it contains ABCBA and PBCBP.

Hope it helps.

[A1]

I don't really understand this problem!
The problem statement say these:
1. A palinword is a string of characters that contains at least 2 different palindromes each with a length of at least 3
2. Here the position is immaterial: the same palindrome occurring in another position is NOT considered as different
3. Neither of these 2 palindromes may be embedded in the other palindrome (for example the palindrome `mum' is embedded in the palindrome `amuma', and `aaa' is embedded in `aaaa') but they may partially overlap

so tell me how these two words are Palinword:

AMAMA MUMMUM

because of the second rule we can not count AMA or MUM twice and ofcourse third rule stop us to count MAM and AMAMA as 2 different plaindromes, same thing apply for UMMU MUMMUM.

actually what i understand from the second and third rule is "A word which is fully palindrome cann't be a Palinword".
what is u opinio?

[Observer]

How about:
AMAMA -> AMA and MAM
MUMMUM -> MUM and UMMU
? Note: I haven't attempted this problem.

[A1]

oppss!! I just missed that
Thankx

[stcheung]

Well I am not familiar with C enough to understand your code. But I notice you have "char aux[257]; " inside a double for loop. This kind of repeated array declaration might take a lot of time. You can try submitting a program that only reads input and then do nothing except to declare this array in your double for loop. See if that itself would cause TLE already.

Also, I think this problem demands a lot of optimizations. So if you think your implementation is the straightforward kind, it might possibly not be fast enough. But again, I can't judge whether your algorithm is fast enough because I didn't really read your code.