IOI'96
The structure of some biological objects is represented by the sequence of their constituents, where each part is denoted by an uppercase letter. Biologists are interested in decomposing a long sequence into shorter sequences called primitives.
We say that a sequence S can be composed from a given set of primitives P if there is a some sequence of (possibly repeated) primitives from the set whose concatenation equals S. Not necessarily all primitives need be present. For instance the sequence ABABACABAABcan be composed from the set of primitives
{A, AB, BA, CA, BBC}
The first K characters of S are the prefix of S with length K. Write a program which accepts as input a set of primitives and a sequence of constituents and then computes the length of the longest prefix that can be composed from primitives.
PROGRAM NAME: prefix
INPUT FORMAT
First, the input file contains the list (length 1..200) of primitives (length 1..10) expressed as a series of space-separated strings of upper-case characters on one or more lines. The list of primitives is terminated by a line that contains nothing more than a period (`.'). No primitive appears twice in the list. Then, the input file contains a sequence S (length 1..200,000) expressed as one or more lines, none of which exceeds 76 letters in length. The "newlines" (line terminators) are not part of the string S.
SAMPLE INPUT (file prefix.in)
A AB BA CA BBC . ABABACABAABC
OUTPUT FORMAT
A single line containing an integer that is the length of the longest prefix that can be composed from the set P.
SAMPLE OUTPUT (file prefix.out)
11
题意:
给出一系列单词(1 ~ 200),每个单词长度 1 ~ 10,直到输入“ . ”表示结束。后给出一个字符串(1 ~ 200000),输出字符串最长的前缀长度,这个前缀能由给出的单词组成。
思路:
字典树存储单词,后在字典树上DFS,同时剪枝。标记单词构成的每段字符串来剪枝,不然会超时。
AC:
/* TASK:prefix LANG:C++ ID:sum-g1 */ #include <string.h> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef struct no { struct no *next[30]; int temp; }node; char aim[200050]; int test[200050]; int max_len,len; node *creat_node() { node *p = new node; for(int i = 0;i < 30;i++) p -> next[i] = NULL; p -> temp = 0; return p; } void insert_str(char *str,node *head) { int str_len = strlen(str); node *p = head; for(int i = 0;i < str_len;i++) { int c = str[i] - 'A'; if(p -> next[c] == NULL) p -> next[c] = creat_node(); p = p -> next[c]; } p -> temp = 1; return; } void dfs(int idex,node *head) { if(idex > max_len) max_len = idex; if(idex == len) return; //若当前下标等于目标串长度则返回 if(test[idex]) return; test[idex] = 1; //test 数组标记状态 int i = idex,k = aim[i] - 'A'; node *p = head; while(p -> next[k] != NULL) { i++; p = p -> next[k]; if(i < len) k = aim[i] - 'A'; //若i == len时也访问数组的话会数组越界 if(p -> temp) dfs(i,head); //凡是单词都搜索一遍,以下一个下标开始 //若是最后一个字母也会进行向下搜索 if(!p -> temp && i == len) return; //当为最后一个字母却不是单词时返回 } return; } int main() { freopen("prefix.in","r",stdin); freopen("prefix.out","w",stdout); char vab[50],str[200]; node *head = creat_node(); max_len = 0; memset(test,0,sizeof(test)); while(~scanf("%s",vab) && vab[0] != '.') { insert_str(vab,head); } while(~scanf("%s",str)) { strcat(aim,str); } len = strlen(aim); dfs(0,head); printf("%d\n",max_len); return 0; }
相关推荐
LeetCode Longest Common Prefix解决方案
北大POJ2533-Longest Ordered Subsequence 解题报告+AC代码
LMS Longest Monotonically Increasing Sequence Algorithm
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Java AC 版本
关于Longest Common Subsequences演算法
这是动态规划中,求最长公共子序列(Longest common string)的源代码。自己编写执行。程序简单,有注释。
北大POJ2533-Longest Ordered Subsequence【O(nlogn)】
Longest Ordered Subsequence,算法分析与设计,C语言程序
Longest Common Ancestor classic ppt...
在Linux操作系统中,内核中有一个...本文将简要介绍Linux系统中的路由表、路由策略以及路由决策的过程,介绍"最长前缀匹配(Longest Prefix Match)"算法,并提供一个完整的源代码来模拟这个算法在路由查找中的应用。
Pku acm 第2533题 Longest Ordered Subsequence 代码,有详细的注释,动态规划
2. The list of remotes is now scanned for longest prefix match first. 3. Support for multipacket TSIG signatures for transfers was added, and incorrectly parsed TSIG key secrets without quotes were...
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...
LCS(longest common substring)算法,即最大公共子串,它是求两个字符串最长公共子串的问题。大体解法是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长...
1.网络层虚电路(Virtual Circuit)是如何实现分组转发 2.解释最长前缀匹配(Longest Prefix Matching)技术是如何实现分组转
asks for the length of the longest common prefix between suffixes beginning at i and j. A compressed LCE data structure is a data structure that stores T in a compressed form while supporting fast LCE...
求直方图的最大面积,左右两次扫面+剪枝优化 Valid Parentheses 用栈判断括号匹配 Regular Expression Matching 递归匹配 wildcard matching 动态规划 longest common prefix , 简单 valid number, hard, 用有限...
简单的最长前缀匹配应用 接受输入文件的简单应用程序,其中包含 IP 地址定义和到 ASN 编号的对应映射。 该文件在应用程序启动时加载并用于构建 trie。 Trie 是用于使用最长前缀匹配算法进行搜索的结构。...
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. ...
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...