首页 > 代码库 > 字符串 - 近似回文词 --- 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。