题目链接：http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1328
解题报告：中文题题意就不说了。还好数据不大，只有1000，枚举回文串的中心位置，然后向两边扩展，当扩展到 k 大于要求的K的时候停止扩展，不断更新最长的长度跟开始位置最小。我先做了个预处理，先求出了a(S)，然后用一个数组保存了a(S)中的字符在原来的字符串中对应的位置在哪，这样便于字符串比较，而且又可以在O(1)时间得到在原来串中的长度跟开始的位置。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = ;
char tt[maxn],str[maxn];
int loc[maxn],K; char chto(char c)
{
return c >= 'A' && c <= 'Z'? (c+'a'-'A'):c;
}
void StrCmp(char* str,int i,int j,int& left,int& right)
{
int k = ,len = strlen(str);
while(i >= && j < len)
{
if(str[i] != str[j]) k++;
if(k > K)
break;
i--,j++;
}
left = i+;
right = j - ;
}
int kuoleft(int l)
{
l--;
while(l >= && !((tt[l] >= 'A' && tt[l] <= 'Z') || (tt[l] >= 'a' && tt[l] <= 'z')))
l--;
return l+;
}
int kuoright(int r)
{
r++;
int len = strlen(tt);
while(r < len && !((tt[r] >= 'A' && tt[r] <= 'Z') || (tt[r] >= 'a' && tt[r] <= 'z')))
r++;
return r - ;
}
int main()
{
int kase = ;
while(scanf("%d",&K)!=EOF)
{
getchar();
gets(tt);
int f = strlen(tt),len = ;
for(int i = ;i < f;++i)
if((tt[i] >= 'A' && tt[i] <= 'Z') || (tt[i] >= 'a' && tt[i] <= 'z'))
{
str[len] = chto(tt[i]);
loc[len] = i;
len++; //记录这个字符在原来的子串中对应的位置
}
str[len] = NULL;
int s = ,L = ;
for(int l = ;l < len;++l)
{
int left = ,right = ;
StrCmp(str,l-,l+,left,right);
int ll = loc[left],rr = loc[right];
int lt = rr - ll + ;
if(lt > L) L = lt,s = ll;
else if(lt == L && ll < s) s = ll;
if(l < len -)
{
left = right = ;
StrCmp(str,l,l+,left,right);
ll = loc[left],rr = loc[right];
lt = rr - ll + ;
if(lt > L) L = lt,s = ll;
else if(lt == L && ll < s) s = ll;
}
}
printf("Case %d: %d %d\n",kase++,L,s+);
}
return ;
}