首页 - 分类讨论区 - 电脑网络 - 葵花宝典版 -阅读文章 首页
 文章阅读：Re: [转载] CS Interview question [同主题阅读] [版面： 葵花宝典] [作者：Pront] , 2004年12月09日03:26:17 Pront 进入未名形象秀 我的博客  [上篇] [下篇] [同主题上篇] [同主题下篇]
 发信人: Pront (阿呆), 信区: Programming 标  题: Re: [转载] CS Interview question 发信站: Unknown Space - 未名空间 (Thu Dec  9 03:45:15 2004) WWW-POST 我的程序和你的很象，不过我是这么想的： 对一个字符串，从左到右，分别以某个字符（或两个字符的中间）为轴， 然后向两边找对应字符，看看最远能走多少。加起来就是了。 如　“222" 2|2 2 2|2|2 2 2|2 #ifdef WIN32 #pragma warning(disable:4786 4101) #define min _MIN #define max _MAX #endif #include #include #include using namespace std; int maxPalindrome(string s) {     int i, j, k;     int count = 0;     for(i = 0; i < s.size(); i++)         for(k = 0; k < 2; k++)             for(j = 1; ; j++)             {                 int x1 = i + k + j;                 int x2 = i - j + 1;                 if (x2 < 0 || x1 >= (int)s.size()                     || s[x1] != s[x2])                 {                     count += j-1;                     break;                 }             }     return count; } int main() {     cout << maxPalindrome("aa") << endl;     cout << maxPalindrome("aabb") << endl;     cout << maxPalindrome("222") << endl;     cout << maxPalindrome("baaab3") << endl;     cout << maxPalindrome("aabbaa") << endl;     return 0; } 【 在 babbage (tm) 的大作中提到: 】 : Let's say that the input string is S, S..S[N] are the chars. : : The question is to find all pairs (i,j) such that: : 1) i=i+2: : : /* 1 */ for k=2 to N-1   // k is (j-i) : /* 2 */   for i=1 to N-k : /* 3 */     A[i][i+k] = A[i+1][i+k-1] && (S[i]==S[j]) : : Now we know if S[i..j] is a palindrome! It takes O(N^2) time. : : This is probably optimal. Because there are strings that contains O(N^2) : palindromes, for example, S= "ABABABABAB...."   (N repetitions of AB, : where every odd-length substring is a palindrome. : : : : : : : : : : : 【 在 lhict (至少还有我) 的大作中提到: 】 : : : Create a function findPalin() that takes a string of characters as argument : : and returns the number of palindromes (a string in which the sequence of cha : : racters is the same forwards and backwards) in that string. There is no spec : : ial character. This function should be as fast as possible. : : Ex: : : "aa" returns 1 : : "aabb" returns 2 : : "222" returns 3 : : "baaab3" returns 4 : : -- ※ 修改:・Pront 於 Dec  9 03:45:15 修改本文・[FROM: 24.16.] ※ 来源:．Unknown Space - 未名空间 mitbbs.com．[FROM: 24.16.]  [上篇] [下篇] [同主题上篇] [同主题下篇]
[转寄] [转贴] [回信给作者] [修改文章] [删除文章] [同主题阅读] [从此处展开] [返回版面] [快速返回] [收藏] [举报]

 标题： 内 容： 将您的链接放在这儿
 友情链接