新鲜出炉~，创新工厂2013-9-25晚在交大的现场笔试题~
1、回文修复
所谓回文，就是正序和倒序遍历结果一样的字符串，比如“aba”，“abcdedcba”。实现一个方法pal()，输入一个字符串，打印出以这个字符串为前缀的一个回文。比如输入“abc”，pal()方法打印出“abcdcba”或“abcba”；输入“abcb”，可以输出“abcbcba”或“abcba”。如果可能，输出尽量短的结果。以Java语言为例：
void pal(String in);
语言任选。
分析：
这道题说白了就是求以给定字符串为前缀的最短回文串。首先我们要明确的是，假设字符串的长度为len，那么最短长度是原字符串的长度len，最长是以最后一个字符为回文中心的回文串长度即2*len-1。
解法一：
枚举插入长度，即0到len-1，每次检测是否为回文，代码如下：
1 #include <cstdlib> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 char in[100001]; 6 char temp[200005]; 7 bool check(char *in) 8 { 9 int len = strlen(in); 10 int i,j; 11 i = 0; 12 j = len-1; 13 while(i<=j) 14 { 15 if(in[i]!=in[j]) 16 return false; 17 else 18 i++,j--; 19 } 20 return true; 21 } 22 23 int main() 24 { 25 freopen("b2.in","r",stdin); 26 freopen("b2.out","w",stdout); 27 int len; 28 int i,j; 29 int iCnt; 30 while (scanf("%s",in)!=EOF) 31 { 32 len = strlen(in); 33 34 for(iCnt = 0; iCnt<len; iCnt++) 35 { 36 strcpy(temp,in); 37 for(i=iCnt-1,j=len; i>=0; i--,j++) 38 { 39 temp[j] = in[i]; 40 } 41 temp[j] = ' '; 42 if(check(temp)) 43 break; 44 } 45 printf("%s ",temp); 46 } 47 return 0; 48 }
解法二：
算法过程如下：
1、使用两个指针b，e分别指向字符串的首末；
2、比较字符，如果相等，则两个指针向内收缩；
如果不等，则将e指针向后移，直到找到相等的，如果找不到，则将e指向最末；
如果找到了，指针再向内收缩；
3、判断，如果b=e(即此时认为这个点是回文中心)，我们检测两端是否相等，如果一直到字符串尾均相等，则可以认为这个点是回文中心，如果到字符串尾还有不相等的，说明还不是回文中心，此时需要将e再向右移，转到2，直至b>=e,退出循环
4、打印in[0]到in[b]和in[e-1]到in[0]。
1 #include <cstdlib> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 char in[100001]; 6 7 int main() 8 { 9 freopen("b2.in","r",stdin); 10 freopen("b2.out","w",stdout); 11 int len; 12 int b,e; 13 while (scanf("%s",in)!=EOF) 14 { 15 len = strlen(in); 16 if (len<=0) continue; 17 b=0; 18 e=len-1; 19 while (b<e) 20 { 21 while (e<len&&in[b]!=in[e]) 22 e++;//尾指针继续推进 23 if (e>=len) 24 b++,e=len-1;//首指针推进，尾指针指向最后 25 else//首尾相同，收缩 26 b++,e--; 27 if(e<=b) 28 { 29 int i=b,j=e; 30 while (j<len&&in[i]==in[j]) 31 i--,j++; 32 if (j<len) e++; 33 } 34 } 35 for (int i=0;i<=b;i++) 36 printf("%c",in[i]); 37 for (int i=e-1;i>=0;i--) 38 printf("%c",in[i]); 39 printf(" "); 40 } 41 return 0; 42 }
PS:本题原题：http://www.spoj.com/problems/EPALIN/，解法一超时，解法二AC。
大家如果有其他想法，欢迎大家评论，共同学习！
补充：此次创新工场笔试的第二道算法题已更新，欢迎访问：http://www.cnblogs.com/codershell/p/3339964.html