emu in blogjava

  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  171 随笔 :: 103 文章 :: 1052 评论 :: 2 Trackbacks
ReverseSubstring
You are given a String input. You are to find the longest substring of 
input such that the reversal of the substring is also a substring of 
input. In case of a tie, return the string that occurs earliest in 
input. 
Definition 
给你一个字符串,你再生成一个颠倒的字符串,从原串中找出任意子串能同时存在颠倒的字符串中, 
求出最长子串 
Class: 
ReverseSubstring 
Method: 
findReversed 
Parameters: 
String 
Returns: 
String 
Method signature: 
String findReversed(String input) 
(be sure your method is public) 
类ReverseSubstring方法  public String findReversed(String input) 


Notes 

The substring and its reversal may overlap partially or completely. 

The entire original string is itself a valid substring (see example 4). 
Constraints 

input will contain between 1 and 50 characters, inclusive. 

Each character of input will be an uppercase letter ('A'-'Z'). 
Examples 
0) 


"XBCDEFYWFEDCBZ" 
Returns: "BCDEF" 
We see that the reverse of BCDEF is FEDCB, which appears later in the 
string. 
颠倒的字符串为"ZBCDEFWYFEDCBX",原串中BCDEF也是颠倒的字符串的子串,并且为最长的 
1) 


"XYZ" 
Returns: "X" 
The best we can do is find a one character substring, so we implement 
the tie-breaker rule of taking the earliest one first. 
2) 


"ABCABA" 
Returns: "ABA" 
The string ABA is a palindrome (it's its own reversal), so it meets the 
criteria. 
3) 


"FDASJKUREKJFDFASIREYUFDHSAJYIREWQ" 
Returns: "FDF" 


4) 


"ABCDCBA" 
Returns: "ABCDCBA" 
Here, the entire string is its own reversal. 
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 2005-12-13 13:35 emu 阅读(1425) 评论(5)  编辑  收藏 所属分类: google编程大赛模拟题及入围赛真题

评论

# re: google中国编程挑战赛资格赛真题 -- ReverseSubstring 2006-08-28 00:59 bitstream
我想询问一下google编程竞赛的情况,以前没参加过,还望不吝赐教。Qualification Round是不是举行一整天?一共有几道题目?比赛用的程序现在能否down下来练练手?
望回复!感谢!  回复  更多评论
  

# re: google中国编程挑战赛资格赛真题 -- ReverseSubstring 2006-08-29 01:21 emu
下个星期的资格赛说明是:
The Qualification Round will be open from Tuesday, September 5, at 12:00 PM (noon) EDT (GMT/UTC -4) through Wednesday, September 6, at 12:00 PM (noon) EDT (GMT/UTC -4). During this 24-hour period, each competitor must complete one randomly generated problem set. All competitors will receive a score for their performance on that one problem set.

如果你已经注册参赛,在确认邮件的 PRACTICING FOR THE EVENT 一段中有关于赛前练手的信息,我收集的题目也可以用来练手。如果你还没有注册就抓紧注册吧,不注册是不能启用competition arena来练手的。  回复  更多评论
  

# re: google中国编程挑战赛资格赛真题 -- ReverseSubstring 2006-08-29 17:12 bitstream
谢谢!
也就是说每人随机抽一套题做。我刚注册了,抽空下点题目看看。你这里的题目我基本都有收集,大多数题不难,只是用的时间太长。(有时间我会把我的解答贴到这里,还望多多指教)
另外,可否就比赛给小弟一些建议?或者谈谈您参赛的经验?
感激不尽!Have a nice day!  回复  更多评论
  

# re: google中国编程挑战赛资格赛真题 -- ReverseSubstring 2006-09-04 20:27 小猫鱼
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class ReverseSubstring {
private static String original="";
public static void main(String[] args) throws IOException {
String s=input();
String s1=reversed(s);
System.out.println(findReversed(Reversedsub(s),Reversedsub( s1))+"结果");
}
static String findReversed(Hashtable orig,Hashtable reversed){

Enumeration enum=orig.elements();
String result=original.substring(0,1);
while(enum.hasMoreElements()){
String s=(String)enum.nextElement();

if( s.equals(reversed.get(s))){
if(s.length()>=result.length()){
result=s;
}

}
}

return result;

}
static Hashtable Reversedsub(String s){
String originals=s;
Hashtable hash=new Hashtable();
for(int m=0;m<originals.length();m++){
for(int i=0;i<originals.length()-m;i++){
String sub= originals.substring(i,i+m+1);

hash.put(sub,sub);
}
}
return hash;
}

static String reversed(String s){
int len=0;
char[] original=s.toCharArray();
len= original.length;
char[] rever=new char[len];
int m=len-1;
for( int i=0;i<=len-1;i++){
rever[i]=original[m];
m--;
}
return new String(rever);
}
static String input() throws IOException{
int first=0;
boolean stop=true;
while(stop){
if(first!=0){
original="输入出错请重新输入";
}
else{
original="请输入数据";
}
System.out.println(original);
BufferedReader input=new BufferedReader(new InputStreamReader(System.in));
original=input.readLine();
if(original.length()==0||original.length()>50){
original="输入出错请重新输入";
}
else{
stop=false;
}
first+=1;
}
return original;
}

}  回复  更多评论
  

# re: google中国编程挑战赛资格赛真题 -- ReverseSubstring 2009-07-11 21:02 Mandy
@小猫鱼
bool Strstr(const char cStr1[], const char cStr2[], int Start, int Count)
{
char *SubString = (char*)malloc(Count + 1);
memcpy(SubString, cStr2+Start, Count);
SubString[Count] = '\0';
char *find = strstr(cStr1, SubString);
free(SubString);
return find == NULL?false:true;
}

int GetSubString(char cStr[], int iSeatCount)
{
int left=0;
int right=iSeatCount-1;
int startindex = 0;
int last = 0;
int templast = 0;
char ch='\0';
char *ReverseSubstring = (char*)malloc(iSeatCount + 1);
memcpy(ReverseSubstring, cStr, iSeatCount + 1);
while(left <= right)
{
ch = ReverseSubstring[left];
ReverseSubstring[left] = ReverseSubstring[right];
ReverseSubstring[right] = ch;
left++;
right = iSeatCount-1-left;
}
ReverseSubstring[iSeatCount] = '\0';
for (int i=0; i<iSeatCount; i++)
{
templast = 1;
while (Strstr(ReverseSubstring, cStr, i, templast) && templast <= iSeatCount - i)
{
templast++;
}
if ((templast - 1) > last)
{
startindex = i;
last = templast - 1;
}
}
printf("The StartPostion is %d and the last number is %d.\n", startindex, last);
printf("The Max Common String is ");
for (i=0; i<last; i++)
{
printf("%c", *(cStr+startindex+i));
}
printf("\n");
return last;
}  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航: