首页 > 代码库 > CSU 1328 近似回文词（2013湖南省程序设计竞赛A题）
CSU 1328 近似回文词（2013湖南省程序设计竞赛A题）
题目链接：http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1328
解题报告：中文题题意就不说了。还好数据不大，只有1000，枚举回文串的中心位置，然后向两边扩展，当扩展到 k 大于要求的K的时候停止扩展，不断更新最长的长度跟开始位置最小。我先做了个预处理，先求出了a(S)，然后用一个数组保存了a(S)中的字符在原来的字符串中对应的位置在哪，这样便于字符串比较，而且又可以在O(1)时间得到在原来串中的长度跟开始的位置。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 const int maxn = 1005; 7 char tt[maxn],str[maxn]; 8 int loc[maxn],K; 9 10 char chto(char c)11 {12 return c >= ‘A‘ && c <= ‘Z‘? (c+‘a‘-‘A‘):c;13 }14 void StrCmp(char* str,int i,int j,int& left,int& right)15 {16 int k = 0,len = strlen(str);17 while(i >= 0 && j < len)18 {19 if(str[i] != str[j]) k++;20 if(k > K)21 break;22 i--,j++;23 }24 left = i+1;25 right = j - 1;26 }27 int kuoleft(int l)28 {29 l--;30 while(l >= 0 && !((tt[l] >= ‘A‘ && tt[l] <= ‘Z‘) || (tt[l] >= ‘a‘ && tt[l] <= ‘z‘)))31 l--;32 return l+1;33 }34 int kuoright(int r)35 {36 r++;37 int len = strlen(tt);38 while(r < len && !((tt[r] >= ‘A‘ && tt[r] <= ‘Z‘) || (tt[r] >= ‘a‘ && tt[r] <= ‘z‘)))39 r++;40 return r - 1;41 }42 int main()43 {44 int kase = 1;45 while(scanf("%d",&K)!=EOF)46 {47 getchar();48 gets(tt);49 int f = strlen(tt),len = 0;50 for(int i = 0;i < f;++i)51 if((tt[i] >= ‘A‘ && tt[i] <= ‘Z‘) || (tt[i] >= ‘a‘ && tt[i] <= ‘z‘))52 {53 str[len] = chto(tt[i]);54 loc[len] = i;55 len++; //记录这个字符在原来的子串中对应的位置 56 }57 str[len] = NULL;58 int s = 0,L = 0;59 for(int l = 0;l < len;++l)60 {61 int left = 0,right = 0;62 StrCmp(str,l-1,l+1,left,right);63 int ll = loc[left],rr = loc[right];64 int lt = rr - ll + 1;65 if(lt > L) L = lt,s = ll;66 else if(lt == L && ll < s) s = ll;67 if(l < len -1)68 {69 left = right = 0;70 StrCmp(str,l,l+1,left,right);71 ll = loc[left],rr = loc[right];72 lt = rr - ll + 1;73 if(lt > L) L = lt,s = ll;74 else if(lt == L && ll < s) s = ll;75 }76 }77 printf("Case %d: %d %d\n",kase++,L,s+1);78 }79 return 0;80 }
CSU 1328 近似回文词（2013湖南省程序设计竞赛A题）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。