文字列-類似の回文語---cs 1328
2504 ワード
近似的な回文語
Problem's Link:http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1328
Mean:
省略する
アナリゼ:
直接暴力でゴールを列挙し、リターンの半径を列挙すればいいです。
Time complexity:O(n*m)
ソースコード:
Problem's Link:http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1328
Mean:
省略する
アナリゼ:
直接暴力でゴールを列挙し、リターンの半径を列挙すればいいです。
Time complexity:O(n*m)
ソースコード:
// 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 long
using 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
",cas++,max_len,sta+1);
}
return 0;
}