s*********l
发帖数: 103 | 1 http://fayaa.com/tiku/view/167/
问题1：
给定两个序列A和B(A,B可以是字符串，也可以是其它类型的一维数组),求B中最短的包
含A的子序列(i.e. the shortest subsequence of B which is the supersequence of
A)。这里'包含'的意思指被包含的
序列(subsequence)可以由包含序列(supersequence)删除一些位置上的元素而得到，而
且顺序必须保持一致。
比如对输入
A: 'hello world'
B: 'hello our world hello my world'
输出应为'hello my world'.
另外当A固定,而B变化巨多或者B固定而A变化居多时应如何处理以提高性能？
问题2：
给定一段文本text和一些关键字集合keywords，求文本text中包含所有keywords的最短
子段落。这里
关键字出现的顺序不重要。比如对输入
text: 'hello our world hello my world'
pattern: {'hello','world'}
输 | a********a
发帖数: 219 | 2 给自己积点福。
int match[100][100];
string sub(string a, string b) {
int oo = 10000000001;
int mn = oo;
int pos = -1;
memset(match, oo, sizeof(match));
memset(match[0], 0, sizeof(match[0]));
for(int i = 1; i <= b.size(); i ++)
for(int k = 1; k <= a.size(); k ++) {
match[k][i] = match[k - ((b[i - 1] == a[k - 1]) ? 1 : 0)][i - 1]
+ 1;
pos = ((k == a.size() && match[k][i] < mn) ? i : pos);
mn = (pos == i) ? match[k][i] : mn;
}
return (mn == o
【在 s*********l 的大作中提到】
: http://fayaa.com/tiku/view/167/
: 问题1：
: 给定两个序列A和B(A,B可以是字符串，也可以是其它类型的一维数组),求B中最短的包
: 含A的子序列(i.e. the shortest subsequence of B which is the supersequence of
: A)。这里'包含'的意思指被包含的
: 序列(subsequence)可以由包含序列(supersequence)删除一些位置上的元素而得到，而
: 且顺序必须保持一致。
: 比如对输入
: A: 'hello world'
: B: 'hello our world hello my world'
| x***y
发帖数: 633 | 3 1. You can use LCS, backtracking and take the one with minimum sequence in B or
using the elements in A(assume A is fixed) as key of hash table, and then
hash elements in B(assume B varies a lot) with the index as the hash value,
and try all the indice in the sequential way to find the answer.( for
example, find the first index of h, then the next possbile index of e, and
go on, find a length and corresponding lower index and upper index of the
subsequence; then starting from next index of h, re
【在 s*********l 的大作中提到】
: http://fayaa.com/tiku/view/167/
: 问题1：
: 给定两个序列A和B(A,B可以是字符串，也可以是其它类型的一维数组),求B中最短的包
: 含A的子序列(i.e. the shortest subsequence of B which is the supersequence of
: A)。这里'包含'的意思指被包含的
: 序列(subsequence)可以由包含序列(supersequence)删除一些位置上的元素而得到，而
: 且顺序必须保持一致。
: 比如对输入
: A: 'hello world'
: B: 'hello our world hello my world'
|
|
