emu in blogjava
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  171 随笔 :: 103 文章 :: 1052 评论 :: 2 Trackbacks
500分模拟题 MaximalPalindromeSubstrings

Problem Statement

    

A palindrome is a string that reads the same forward and backward. A palindrome substring is a contiguous sequence of characters taken from a string that form a palindrome. A palindrome substring of a string is maximal if we can't extend it to get a bigger palindrome substring. For example, string "acdadc" has 2 maximal palindrome substrings - "a" (the first one) and "cdadc". All other palindrome substrings (like "dad" or "c") can be extended to "cdadc", so they are not maximal.

You will be given a String[] str. Concatenate the elements of str to form one long string, and return the number of maximal palindrome substrings contained in that string.

Definition

    
Class: MaximalPalindromeSubstrings
Method: countMaximalPalindromeSubstrings
Parameters: String[]
Returns: int
Method signature: int countMaximalPalindromeSubstrings(String[] str)
(be sure your method is public)
    

Constraints

- str will contain between 1 and 50 elements, inclusive.
- Each element of str will contain between 1 and 50 characters, inclusive.
- Each character of each element of str will be a lowercase letter ('a'-'z').

Examples

0)
     
{"acdadc"}
 
Returns: 2
The example from the problem statement.
1)
     
{"ababab"}
 
Returns: 2
The two maximal palindrome substrings here are "ababa" and "babab".
2)
     
{"aaaa","bbb","axxx"}
 
Returns: 3
Remember to use the whole input!
3)
     
{"abacabbacaacdbdcacxcbbbbcabababacccbazhhaahh"}
 
Returns: 14

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

posted on 2006-09-05 10:20 emu 阅读(1920) 评论(3)  编辑  收藏 所属分类: google编程大赛模拟题及入围赛真题

评论

# re: 500分模拟题 MaximalPalindromeSubstrings 2006-10-17 15:53 oldglost
是不是用动态规划来做？
任何一个符合题意的字串，要么有一个中心字符，要么两个两个相邻字符相同
因此，
1，把每个字符，或者每两个相邻字符相同的pair记录到一个集合
2，对1的集合中所有元素，向左右个扩展一个字符，如果这两个字符相同则记录，不同则计数，并扔出集合。
循环直到全部元素被扔出。
  回复  更多评论
  

# re: 500分模拟题 MaximalPalindromeSubstrings 2006-11-19 18:05 zwgoal
我的python解法：


def MaximalPalindromeSubstrings(s):
xxflag=-1
count=0
for i in range(0,len(s)):
sta=i
sed=flag=len(s)-1

while sed>sta and flag>xxflag:

if s[sta]==s[sed]:
sed-=1
sta+=1
continue
else:
sta=i
sed=flag
sed-=1
flag-=1
if flag>xxflag:
count+=1
xxflag=flag

if sta==sed:
print s[(flag-2*(flag-sta)):(flag+1)]
if sta>sed:
print s[((flag-2*(flag-sta))-1):(flag+1)]
if xxflag==len(s)-1:
break
return count
xx='abacabbacaacdbdcacxcbbbbcabababacccbazhhaahh'
ret=MaximalPalindromeSubstrings(xx)

print 'count:',ret
  回复  更多评论
  

# re: 500分模拟题 MaximalPalindromeSubstrings 2007-12-27 14:16 jjww
public static int countMaximalPalindromeSubstrings(String[] str)
{

String target = "";
int length = str.length;
for (int i=0; i< length;i++)
{
target += str[i];
}
length = target.length();

int head = 0;
int tail = length -1;

char c1,c2;
int head_tmp = head;
int tail_tmp = tail;
boolean recover = false;
int count =0;
int h_length =0;
int last_h_length =0;
boolean finished = false;

for (;!finished;head++)
{

h_length = 0;
c1 = target.charAt(head);

head_tmp = head;

int head1 = head_tmp;
int tail1 = tail;

for (tail_tmp = tail;head_tmp<tail_tmp;)
{
if (recover)
{
h_length=0;
head_tmp = head1;
tail1--;
tail_tmp = tail1 ;
}

c1 = target.charAt(head_tmp);
c2 = target.charAt(tail_tmp);
if (c1 == c2)
{
recover = false;
head_tmp ++;
tail_tmp --;
h_length +=2;
continue;
}
else
{
recover = true;

}
}
if (tail1 == length-1)
{
finished = true;
}
if (head_tmp==tail_tmp)
{
h_length += 1;
}
else if (Math.abs(head_tmp-tail_tmp) == 2)
h_length -= 1;

if (last_h_length < head + h_length)
{
count ++;
last_h_length = h_length+head;
}
}


return count;

}  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: