csu1328（近似回文串）

本文主要是介绍csu1328（近似回文串），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：求近似回文串的最大长度，串长度为1000。

解题思路：以某点为中心，向左右两边扩展，注意奇偶分开讨论，暴力解即可。时间复杂度O(n^2);

代码如下：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<cstring>
#include<string>
#include<vector>
#define N 1005
#define inf 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 10e-6using namespace std;
char s[N],str[N];
int num[N];
int main()
{int k,cas = 1;while(scanf("%d",&k) != EOF){getchar();gets(s);int i,j,tot = 0;int len = strlen(s);for(i = 0; i < len; i++){if(s[i] >= 'a' && s[i] <= 'z') str[tot] = s[i],num[tot++] = i;else if(s[i] >= 'A' && s[i] <= 'Z') str[tot] = s[i]+32,num[tot++] = i;}str[tot] = '\0';//  cout<<str<<endl;//       for(i = 0; i < tot; i++)   cout<<num[i]<<" ";//     cout<<endl;int ans = -1,id;// cout<<tot<<endl;for(i = 0; i < tot; i++){//cout<<i<<endl;int cnt = 0;for(j = 1; ; j++){if(i-j < 0 || i+j >= tot)   break;if(str[i-j] != str[i+j])   cnt++;if(cnt > k)    break;}j--;if(num[i+j] - num[i-j] + 1 > ans)  {ans = num[i+j] - num[i-j] + 1;id = num[i-j];}if(i+1 != tot){cnt = 0;if(str[i] != str[i+1]) cnt++;if(cnt > k)    continue;int l = i-1,r = i+2;while(1){if(l < 0 || r >= tot)  break;if(str[l] != str[r])   cnt++;if(cnt > k)    break;l--;r++;}l++;r--;if(num[r] - num[l] + 1 > ans){ans = num[r] - num[l] + 1;id = num[l];}}}printf("Case %d: %d %d\n",cas++,ans,id+1);}return 0;
}

这篇关于csu1328（近似回文串）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---