Calf Flac（枚举）

 

Calf Flac

It is said that if you give an infinite number of cows an infinite number of heavy-duty laptops (with very large keys), that they will ultimately produce all the world's great palindromes. Your job will be to detect these bovine beauties.

Ignore punctuation, whitespace, numbers, and case when testing for palindromes, but keep these extra characters around so that you can print them out as the answer; just consider the letters `A-Z' and `a-z'.

Find the largest palindrome in a string no more than 20,000 characters long. The largest palindrome is guaranteed to be at most 2,000 characters long before whitespace and punctuation are removed.

PROGRAM NAME: calfflac

INPUT FORMAT

A file with no more than 20,000 characters. The file has one or more lines which, when taken together, represent one long string. No line is longer than 80 characters (not counting the newline at the end).

SAMPLE INPUT (file calfflac.in)

Confucius say: Madam, I'm Adam.

OUTPUT FORMAT

The first line of the output should be the length of the longest palindrome found. The next line or lines should be the actual text of the palindrome (without any surrounding white space or punctuation but with all other characters) printed on a line (or more than one line if newlines are included in the palindromic text). If there are multiple palindromes of longest length, output the one that appears first.

SAMPLE OUTPUT (file calfflac.out)

11
Madam, I'm Adam

   题意：

   给出一个字符串句子，找出这个字符串最大的回文串数量，并输出这个回文串语句（判断回文串是不包括标点符号和空格在内的）。

 

   思路：

   一个个点进行查找，从该点开始向左右扩展找出最大回文串值，并记录首和尾的位置。回文串分为两种情况，分别为奇数和偶数的情况，分别计算和统计。

 

   first and wrong：

 

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define BOR 20000+5

int same(char a,char b)
{
	if(a==b) return 1;
	if(a==b-32) return 1;
	if(a-32==b) return 1;
	return 0;
}

int main()
{
	char pos[BOR];
	int i,length,max=0,l,r,sum,from,to;
	gets(pos);
	length=strlen(pos);

//    printf("\n%s\n",pos);
//循环不是从0开始的，所以如果数组只有pos[0]的话，则程序会出现错误	
	for(i=1;i<length;i++)
	{
		if((pos[i]<'A'||pos[i]>'Z')&&(pos[i]<'a'||pos[i]>'z')) continue;
		l=i-1;
		r=i+1;
		sum=1;
//这是只有回文串是单数的时候的情况		
//		printf("\nr=%d\n",r);
//		printf("%c",pos[11]);
		
		while((pos[l]<'A'||pos[l]>'Z')&&(pos[l]<'a'||pos[l]>'z')&&l>=0) l--;
		while((pos[r]<'A'||pos[r]>'Z')&&(pos[r]<'a'||pos[r]>'z')&&(r<length)) r++;
//这里的判断条件没有=，细心！		
//		printf("\nl=%d\nmid=%d\nr=%d\n",l,i,r);
//		system("pause");
		
		while(l>=0&&r<length&&same(pos[l],pos[r]))
		{
			sum+=2;
			l--;
			r++;
			while((pos[l]<'A'||pos[l]>'Z')&&(pos[l]<'a'||pos[l]>'z')&&l>=0) l--;
			while((pos[r]<'A'||pos[r]>'Z')&&(pos[r]<'a'||pos[r]>'z')&&r<length) r++;
		
//			printf("\nl=%d\nr=%d\n",l,r);
//			printf("sum=%d\n",sum);
//			system("pause");
		}
		
		if(sum>max) 
		{
		 max=sum;
	     from=l+1;
	     to=r-1;
		}
		
//		printf("\nl=%d\nr=%d\n",l,r);
//		printf("max=%d\n",max);
//		system("pause");
	}
	
//	printf("\nfrom=%d\nto=%d\n",from,to);

	while((pos[from]<'A'||pos[from]>'Z')&&(pos[from]<'a'||pos[from]>'z')&&from>=0) from++;
	while((pos[to]<'A'||pos[to]>'Z')&&(pos[to]<'a'||pos[to]>'z')&&to<length) to--;
//方法可行
//但是存在许多容易出错的地方，而且循环从1开始，故会忽略许多情况
//比如但数组长度只有1的时候	
    printf("%d\n",max);
	for(from;from<=to;from++)
	 printf("%c",pos[from]);
	printf("\n");
//	system("pause");
	return 0;
}

   AC：

 

 

#include<stdio.h>
#include<string.h>
#define BOR 20000+5
//判断是否相等的函数
int same(char a,char b)
{
	if(a==b||a-32==b||a==b-32) return 1;
	return 0;
}

int main()
{
    freopen("calfflac.in","r",stdin);
    freopen("calfflac.out","w",stdout);
	
	char pos[BOR]={0},cr[BOR]={0};
	char line[85];
	int length,i,l,r;
	int from,to,max=0,sum;
//输入部分，看清题意应如何输入字符串的
	while(gets(line)!=NULL) 
	{
      strcat(pos,line); 
	  cr[strlen(pos)-1]=1;
    }
    length=strlen(pos);
    
    
	for(i=0;i<length;i++)
    {
      if((pos[i]<'A'||pos[i]>'Z')&&(pos[i]<'a'||pos[i]>'z')) continue;
	  
//当回文串为奇数的时候 
	  l=i;
	  r=i;
	  sum=-1;
//巧设，令一开始都为自己本身，长度为-1
      while(l>=0&&r<=length-1)
	  {
	  	if(!same(pos[l],pos[r])) break;
	  	sum+=2;
	if(sum>max)
        {
      	max=sum;
      	from=l;
      	to=r;
        }
//比较函数应该在循环内进行，因为循环到这一步的时候，pos[ l ],pos[ r ]不应该是标点符号值
//切它们是相等的字符值，故sum+=2后马上进行判断处理
	  	l--;
	  	r++;
//判断完后，左编号继续做进，右编号仅需后进
	  	while((pos[l]<'a'||pos[l]>'z')&&(pos[l]<'A'||pos[l]>'Z')&&l>=0)  l--;
	  	while((pos[r]<'a'||pos[r]>'z')&&(pos[r]<'A'||pos[r]>'Z')&&r<=length-1) r++;
	  }	


//当回文串为偶数的时候    
      l=i;
	  r=i+1;
	  sum=0;
      while(l>=0&&r<=length-1)
	  {
	  	if(!same(pos[l],pos[r])) break;
	  	sum+=2;
	  	if(sum>max)
        {
      	max=sum;
      	from=l;
      	to=r;
        }	
	  	l--;
	  	r++;
//比较完后，左编号前进一个，右编号后进一个
//前后进后，此时的pos[ l ],pos[ r ]不一定不是标点符号和空格
	  	while((pos[l]<'a'||pos[l]>'z')&&(pos[l]<'A'||pos[l]>'Z')&&l>=0)  l--;
	  	while((pos[r]<'a'||pos[r]>'z')&&(pos[r]<'A'||pos[r]>'Z')&&r<=length-1) r++;
//忽略当前值为标点为标点符号或者为空格的情况
	  }	
	  
    }
	
	printf("%d\n",max);
	for(i=from;i<=to;i++) 
	{
        printf("%c",pos[i]);
        if(cr[i]==1) printf("\n");
    }
    if(cr[to]!=1) printf("\n");
//最终输出
    return 0;
}

   总结：

 

   题意非常简单，但是实现方面却很棘手，没 有特别技巧的方法，只能这样子一一列举出来，需要更加细心，更加清晰每一步的操作有什么作用，会带来什么后果。考虑好数组边界问题，哪一步操作应先进行还是后进行。每一个点都要思考清楚才能着手。分析问题还是很容易就分析少了某几种特殊情况，还需继续努力啊。（注意这题的输入，每80个字符为一行，最终组成一个大的字符串数组）。

   这题也存在有技巧性的地方：

   比如测试奇数回文串的时候运用 l=r=i;sum=-1;这样赋值的话，数组的循环数就可以大胆地从0开始算起，并且如果第一项满足的话也是sum+=2，从而使sum=1，根据判断while(l>=0&&r<=length-1)来决定是否循环一下操作；

   同理测试偶数回文串的时候运用l=i;r=i+1;sum=0。