p*******9
发帖数: 1860 | 1 有一个问题请教论坛里的脚本语言和编程高手。
今有两个文件：文件A里面有100个关键词，文件B里面有5000行的文本。任务是在文件B
中查找文件A里的关键词，如果文件A里的关键词出现在文件B中，则把该关键词输入到
文件C中。请问如何实现？
文件A（关键词）：
----------------------------------------
Apple
Banana
Can
Delta
...
----------------------------------------
文件B（文本）:
----------------------------------------
define: apple
get 100 Delta
...
-----------------------------------------
文件C（结果）:
-----------------------------------------
Apple
Delta
----------------------------------------- |
m*d
发帖数: 7658 | 2 作业题拿到论坛上来问
件B
【在 p*******9 的大作中提到】
: 有一个问题请教论坛里的脚本语言和编程高手。
: 今有两个文件：文件A里面有100个关键词，文件B里面有5000行的文本。任务是在文件B
: 中查找文件A里的关键词，如果文件A里的关键词出现在文件B中，则把该关键词输入到
: 文件C中。请问如何实现？
: 文件A（关键词）：
: ----------------------------------------
: Apple
: Banana
: Can
: Delta
|
C****i
发帖数: 1776 | 3 隔壁有个 unix linux programming版，
【在 m*d 的大作中提到】
: 作业题拿到论坛上来问
:
: 件B
|
l******n
发帖数: 1683 | 4 grep -o -f A B > C
件B
【在 p*******9 的大作中提到】
: 有一个问题请教论坛里的脚本语言和编程高手。
: 今有两个文件：文件A里面有100个关键词，文件B里面有5000行的文本。任务是在文件B
: 中查找文件A里的关键词，如果文件A里的关键词出现在文件B中，则把该关键词输入到
: 文件C中。请问如何实现？
: 文件A（关键词）：
: ----------------------------------------
: Apple
: Banana
: Can
: Delta
|
s*****n
发帖数: 5488 | 5 面试题吧。
naive方法 O(nm)复杂度。
要是想提高.
1. 建立关键词的prefix tree T.然后从文件B过 T, 一旦找到某个 W \in A.
A = A - W. cut the path of W from T.
until 1). end of the B OR 1) T is empty.
最差复杂度还是O(nm).实际要好的多。
2. 用B的题开查询A的hash table. averagew O(n)复杂度。
件B
【在 p*******9 的大作中提到】
: 有一个问题请教论坛里的脚本语言和编程高手。
: 今有两个文件：文件A里面有100个关键词，文件B里面有5000行的文本。任务是在文件B
: 中查找文件A里的关键词，如果文件A里的关键词出现在文件B中，则把该关键词输入到
: 文件C中。请问如何实现？
: 文件A（关键词）：
: ----------------------------------------
: Apple
: Banana
: Can
: Delta
|
s*****n
发帖数: 5488 | 6 3.建立两个prefix tree T T'. Matching T & T'.应该O(n)最差时间久可以搞定了。
【在 s*****n 的大作中提到】
: 面试题吧。
: naive方法 O(nm)复杂度。
: 要是想提高.
: 1. 建立关键词的prefix tree T.然后从文件B过 T, 一旦找到某个 W \in A.
: A = A - W. cut the path of W from T.
: until 1). end of the B OR 1) T is empty.
: 最差复杂度还是O(nm).实际要好的多。
: 2. 用B的题开查询A的hash table. averagew O(n)复杂度。
:
: 件B
|
