toj_2902.cpp

Tianjin University Online Judge 的80多道题目 .

/*2902.   palindrome 
--------------------------------------------------------------------------------
Time Limit: 1.0 Seconds   Memory Limit: 65536K
Total Runs: 58   Accepted Runs: 47

--------------------------------------------------------------------------------



A palindrome is a sequence of one or more characters that reads the same from the left as it does from the right. For example, SHAHS are palindromes, but SHAKS is not. 

Your job, should you choose to accept it, is to write a program that reads a sequence of strings and for each string determines the number of UNIQUE largest palindromes that are substrings and also print the largest length.

Input and Output:

The input file consists of a number of strings (one per line), of at most 80 characters each, starting in column 1. Strings contain only upper case letters. For each non-empty input line,the output consists of one line containing the largest length of the palindromes and the number of UNIQUE largest palindromes.

Sample Input:

SHAKIL
BABU
BABUAAA

Sample Output:

1 6
3 1
3 2



Problem Setter: MD. SHAKIL AHMED. (CUET AGRODUT)



Source: New Year Challenge Contest*/
#include<cstdio>
#include<cstring>
#define MAX 100

int palindrome( char const str[] , int const len )
{
  int i , j , lenD2;
  bool flag;
  lenD2 = len / 2;
  for ( flag = true , i = 0; i < lenD2; i++ )
    {
      if ( str[ i ] != str[ len - 1 - i ] )
	{
	  flag = false;
	  break;
	}
    }
  return flag;
}

int main()
{
  char str[ MAX ] , aStr[ MAX ] , subseq[ MAX ][ MAX ];
  int i , j , k ,  num  , len1 , len2;
  bool flag , flagExist;
  while ( scanf( "%s" , str ) != EOF )
    {
      len1 = strlen( str );
      for ( i = len1; i >= 1; i-- )
	{
	  for ( flag = false , num = 0 , j = 0; j <= len1 - i; j++ )
	    {
	      memcpy( aStr , &str[ j ] , i );
	      aStr[ i ] = '\0';
	      //	      printf( "%s\n" , aStr );
	      len2 = strlen( aStr );
	      if ( palindrome( aStr , len2 ) )
		{
		  flag = true;
		  //		  printf( "flag = %d\n" , flag );
		  for ( flagExist = false , k = 0; k < num; k++ )
		    {
		      if ( strcmp( subseq[ k ] , aStr ) == 0 )
			{
			  flagExist = true;
			  break;
			}
		    }
		  if ( !flagExist )
		    {
		      strcpy( subseq[ num ]  , aStr );
		      num++;
		    }
		}
	    }
	  if ( flag ) break;
	}
      printf( "%d %d\n" , i  , num );
    }
  return 0;
}