请教脚本和编程高手：关键字自动查找与输出 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PDA - 掌中宝

请教脚本和编程高手：关键字自动查找与输出

请教脚本和编程高手：关键字自动查找与输出# PDA - 掌中宝

p*92012-09-10 07:09

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*d2012-09-10 07:09

2 楼

作业题拿到论坛上来问

件B

【在 p*******9 的大作中提到】

: 有一个问题请教论坛里的脚本语言和编程高手。
: 今有两个文件：文件A里面有100个关键词，文件B里面有5000行的文本。任务是在文件B
: 中查找文件A里的关键词，如果文件A里的关键词出现在文件B中，则把该关键词输入到
: 文件C中。请问如何实现？
: 文件A（关键词）：
: ----------------------------------------
: Apple
: Banana
: Can
: Delta

C*i2012-09-10 07:09

3 楼

隔壁有个 unix linux programming版，

【在 m*d 的大作中提到】

: 作业题拿到论坛上来问
:
: 件B

l*n2012-09-10 07:09

4 楼

grep -o -f A B > C

件B

【在 p*******9 的大作中提到】

s*n2012-09-10 07:09

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 的大作中提到】

s*n2012-09-10 07:09

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