TOJ4959: 近似回文词

叁歲伎倆 2022-05-30 09:13 128阅读 0赞

描述

输入一行文本，输出最长近似回文词连续子串。所谓近似回文词是指满足以下条件的字符串：  
1. S以字母开头，字母结尾  
2. a(S)和b(S)最多有2k个位置不同，其中a(S)是S删除所有非字母字符并且把所有字母转化成小写之后得到的串，b(S)是a(S)的逆序串。  
比如当k=1时，Race cat是一个近似回文词，因为a(S)=racecat和b(S)=tacecar只有2个位置不同。

输入

输入包含不超过25组数据，每组数据包含两行。第一行是整数k（0<=k<=200），第二行为字符串S，包含至少一个字母但不超过1000个字符（换行符不算）。S只包含字符、空格和其他可打印字符（比如逗号，句号），并且不会以空白字符开头。

输出

对于每组测试数据，输出最长近似回文子串的长度和起始位置（S的第一个字符是位置1）。如果有多个最长近似回文子串解，起始位置应尽量小。

样例输入

1  
Wow, it is a Race cat!  
0  
abcdefg  
0

Kitty: Madam, I'm adam.

样例输出

Case 1: 8 3  
Case 2: 1 1

Case 3: 15 8

别看题目提出了一个新的概念“近似”，其实还是找回文串而已，就是以往不匹配直接break，变成了计数至k再break。

#include<stdio.h>
    #include<string.h>     
    int main()  
    {
    	int k,b,i,j,l,r,o=1,p,maxlen,flag,fal;
    	//maxlen 最长回文 flag起点 
    	char a[1500],ap[1500];
    	int t[1500];//存位置 
    	while(scanf("%d",&k)!=EOF)
    	{
    		getchar();		
    		gets(a);
    		b=strlen(a);
    		p=0;maxlen=-1;flag=-1;
    		for(i=0;i<b;i++)
    		{
    			if(a[i]>='a'&&a[i]<='z')
    			{
    				t[p]=i;
    				ap[p++]=a[i];				 
    			} 
    			else if(a[i]>='A'&&a[i]<='Z')
    			{
    				t[p]=i;
    				ap[p++]=a[i]+32;				 
    			} 
    		}
    		ap[p]='\0';
    		//printf("%s\n",ap);
    		for(i=0;i<p;i++)
    		{
    			fal=0; 
    			for(j=0;i-j>=0&&i+j<p;j++)
    			{
    				//以i为中心，回文串长度为奇数
    				if(ap[i-j]!=ap[i+j])
    				fal++;
    				if(fal>k)break; 
    			}
    			j--;
    			if(t[i+j]-t[i-j]+1>maxlen)//+1是因为下标从0开始 
    			{
    				maxlen=t[i+j]-t[i-j]+1;
    				flag=t[i-j];
    			}
    			fal=0; 
    			for(j=0;i-j>=0&&i+j+1<p;j++)
    			{
    				//回文串长度为偶数
    				if(ap[i-j]!=ap[i+j+1])
    				fal++;
    				if(fal>k)break; 
    			}
    			j--;
    			if(j<=-1)continue;//不存在 
    			if(t[i+j+1]-t[i-j]+1>maxlen)
    			{
    				maxlen=t[i+j+1]-t[i-j]+1;
    				flag=t[i-j];
    			}
    		}
    		printf("Case %d: %d %d\n",o++,maxlen,flag+1);
    	}
    }