首页 > 专题系列 > Java解POJ > POJ 3753 根据关键字进行字符串拷贝 [解题报告] Java
2013
11-13

POJ 3753 根据关键字进行字符串拷贝 [解题报告] Java

根据关键字进行字符串拷贝

问题描述 :

把源字符串拷贝到目的字符串,如果指定关键字,则以该关键字结束(不包括关键字本身),如果拷贝失败,则得到空串。

具体要求:实现如下函数原型SafeStrcpy2KeyWord(),并在代码中调用该函数实现上述功能。该函数的实现要考虑各种可能的参数取值,以确保程序不出现崩溃。


int SafeStrcpy2KeyWord(char* pDestBuffer, //拷贝的目的地地址
char* pSourceString, //拷贝的源地址
int nDestBufferSize, //拷贝的目的地缓冲区长度
char* szKeyWord); //指定关键字符串

返回值:所拷贝的字符串长度。如果拷贝失败,则返回0。

输入:

输入包含多组数据,以EOF结束

每组数据第一行为不含空格的源字符串,长度小于256;接下来的一行或多行都是关键字串(长度小于16),一直到END结束。“NULL”表示关键字串为空,此时输出的拷贝后的长度应为0,拷贝后的字符串为空串(也用”NULL”表示,见下文)。

输出:

对于每组数据输出拷贝的长度和拷贝后的目的字符串,以空格分隔。如果该目的字符串为空,则用”NULL”表示。

样例输入:

/home/tony/work_server/1/rtest/relayer.out
/
/t
/1/r
.
NULL
END

样例输出:

0 NULL
5 /home
22 /home/tony/work_server
38 /home/tony/work_server/1/rtest/relayer
0 NULL

解题代码:

import java.io.BufferedInputStream;   
import java.util.Scanner;   
  
/**  
 *  
 *poj3753  
 * C语言里的  
 * while(EOF != scanf("%s",source))  
 *等价于java里的while (scan.hasNext())  
 * @author NC  
 */  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        while (scan.hasNext()) {   
            String src = scan.nextLine().trim();   
            while (true) {   
                String key = scan.nextLine().trim();   
                if (key.endsWith("END")) {   
                    break;   
                }   
                if (key.equals("NULL")) {   
                    System.out.println("0 NULL");//陷井   
                } else if (key.isEmpty() || key.equals("") || !src.contains(key)) {   
                    System.out.println(src.length() + " " + src);//陷井   
                } else if (src.contains(key)) {   
                    String sub = src.substring(0, src.indexOf(key));   
                    if (src.indexOf(key) == 0) {   
                        System.out.println("0 NULL");//陷井   
                    } else {   
                        System.out.println(sub.length() + " " + sub);   
                    }   
                }   
            }   
        }   
    }   
}

  1. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)