USACO - 2.3.1 - Longest Prefix

 

原创文章转载请注明出处

摘要：动态规划

一. 题目翻译

1. 描述：

在生物学中，一些生物的结构是用包含其要素的大写字母序列来表示的。生物学家对于把长的序列分解成较短的序列（即元素）很感兴趣。

如果一个集合 P 中的元素可以通过串联（元素可以重复使用，相当于 Pascal 中的 “+” 运算符）组成一个序列 S ，那么我们认为序列 S 可以分解为 P 中的元素。元素不一定要全部出现（如BBC就没有出现）。举个例子，序列 ABABACABAAB 可以分解为下面集合中的元素：

{A, AB, BA, CA, BBC}

序列 S 的前面 K 个字符称作 S 中长度为 K 的前缀。设计一个程序，输入一个元素集合以及一个大写字母序列 S ，设S'是序列S的最长前缀，使其可以分解为给出的集合P中的元素，求S'的长度K。

2. 格式：

          INPUT FORMAT:

          输入数据的开头包括 1..200 个元素（长度为 1..10 ）组成的集合，用连续的以空格分开的字符串表示。字母全部是大写，数据可能不止一行。元素集合结束的标志是一个只包含一个 “.” 的行。集合中的元素没有重复。接着是大写字母序列 S ，长度为 1..200,000 ，用一行或者多行的字符串来表示，每行不超过 76 个字符。换行符并不是序列 S 的一部分。

          OUTPUT FORMAT:

          只有一行，输出一个整数，表示 S 符合条件的前缀的最大长度。

3. SAMPLE：

          SAMPLE INPUT:

 A AB BA CA BBC

.

          SAMPLE OUTPUT:

11

          

二.  题解

1. 题意理解（将问题分析清楚，大致用什么思路）：

          这道题目的核心是动态规划。我们使用数组result[i]=1表示字符串S中从1到i的所有字符都可以由集合P中元素组成。那么如果要result[i]=1，那么条件是result[j]=1（j<i），并且字符串S中j到i的字符在集合P中。

 

2. 具体实现（具体实现过程中出现的问题）：

          请参考代码注释。要特别注意程序的输入输出，按照题目描述读取输入。

3. 启示:

          请参考代码注释。要特别注意程序的输入输出，按照题目描述读取输入。

三.  代码

/*
ID:fightin1
LANG:JAVA
TASK:prefix
*/


import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.Scanner;
import java.util.StringTokenizer;

import javax.swing.text.AbstractDocument.LeafElement;

public class prefix {

	public static void main(String[] args) throws Exception {
//		Scanner in = new Scanner(System.in);
//		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
//		PrintWriter pw = new PrintWriter(System.out);
		BufferedReader in = new BufferedReader(new FileReader("prefix.in"));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(
				"prefix.out")));
		HashSet<String> prefix = new HashSet<String>();
		String line = in.readLine();
		while(!line.equals(".")){
			StringTokenizer tokens = new StringTokenizer(line);
			while(tokens.hasMoreTokens()){
				prefix.add(tokens.nextToken());	
			}
			line = in.readLine();
		}
//		while(in.hasNextLine()){
//			line = line + in.nextLine();
//		}
		StringBuffer tmpS = new StringBuffer();
        String readLine2 = in.readLine();
        while (readLine2 != null)
        {
            tmpS.append(readLine2);
            readLine2 = in.readLine();
        }
        line = " "+tmpS.toString();
		
		int[] result = new int[line.length()];
		result[0] = 1;
		String temp;
		int cnt = 0;
		for (int i=1;i<line.length();i++){
			for (int j=i;j>=1;j--){
				if (i-j+1>10){
					break;
				}
				temp = line.substring(j, i+1);
				if (prefix.contains(temp)){
					if (result[j-1]==1){
						result[i] = 1 ;
						break;
					}
				}
			}
		}
		boolean found = false;
		for (int i=line.length()-1;i>0;i--){
			if (result[i]==1){
				pw.println(i);
				found = true;
				break;
			}
		}
		if (!found){
			pw.println(0);
		}
		pw.close();
	}

}