首页 > 代码库 > 字符串 - 近似回文词 --- csu 1328

字符串 - 近似回文词 --- csu 1328

近似回文词

Problem‘s Link:http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1328


 

Mean: 

 略。

analyse:

 直接暴力枚举每一个终点,然后枚举回文串的半径即可。

Time complexity:O(n*m)

 

Source code:

 

// Memory   Time// 1347K     0MS// by : Snarl_jsb// 2014-10-03-14.25#include<algorithm>#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<vector>#include<queue>#include<stack>#include<map>#include<string>#include<climits>#include<cmath>#define N 1000010#define LL long longusing namespace std;int k,real[1100],sta,max_len,cas=1;char st[1100],ss[1100];int main(){    ios_base::sync_with_stdio(false);    cin.tie(0);//    freopen("C:\\Users\\ASUS\\Desktop\\cin.cpp","r",stdin);//    freopen("C:\\Users\\ASUS\\Desktop\\cout.cpp","w",stdout);    while(~scanf("%d",&k))	{		getchar();		gets(st);		int len=0;		max_len=0;		int l1=strlen(st);		for(int i=0;i<l1;++i)		{			if((st[i]>=‘a‘&&st[i]<=‘z‘)||(st[i]>=‘A‘&&st[i]<=‘Z‘))			{				if(st[i]>=‘A‘&&st[i]<=‘Z‘)					st[i]+=32;				ss[len]=st[i];				real[len]=i;				len++;			}		}		for(int i=0;i<len;++i)		{			int error=0,j;			for(j=0;i+j<len&&i-j>=0;++j)			{				if(ss[i+j]!=ss[i-j])					error++;				if(error>k)					break;			}			j--;			if(real[i+j]-real[i-j]+1>max_len)			{				max_len=real[i+j]-real[i-j]+1;				sta=real[i-j];			}			error=0;			for(j=1;i+j<len&&i-j+1>=0;++j)			{				if(ss[i+j]!=ss[i-j+1])					error++;				if(error>k)					break;			}			j--;			if(j<=0) continue;			if(real[i+j]-real[i-j+1]+1>max_len)			{				max_len=real[i+j]-real[i-j+1]+1;				sta=real[i-j+1];			}		}		printf("Case %d: %d %d\n",cas++,max_len,sta+1);	}    return 0;}

  

字符串 - 近似回文词 --- csu 1328