已知一个100万行文本文件，每行固定有m个字符，文本文件中任意两个文本行内容都不重复，现要找出符合如下条件的结果：

1、m>n，n不为0，如果某文本行与另一文本行有且只有n个字符不同，则称此两文本行n互异。

2、若某文本行在文件中有且只有i个n互异文本行，则保留此文本行。

3、找出所有存在i个n互异文本行的文本行。

我的做法是：

1、把100万行文本文件复制一份，设为B，源文件为A；

2、读入A的第k行，与B中逐行比较，比较100万次后看是否n互异文本行数为i，是则保留。

3、k从1到100万循环。

这样要作100万*100万次计算，时间耗费很久，我2.8G的机子要30分钟左右，可是我看网络上有的人实现同样的功能只要1分钟，甚至10几秒。

请高手指点下如何能实现10几秒的速度，是要多线程吗？

懂得话给个算法思路，要不给个相关链接，多谢了！！！！

顶上去

好难啊.我不会,不过那位高手做出来了.我会过来学习学习的.

怎么都没人懂？

你的算法是比较100万*100万次，其实可以更少比一半。（100万+1）*50万次。

文件的前一行与其后的所有行比较，并作计数。

如：查找条件是有8个字符相同的

1。用行1去比行2，行3，行4，行5。符合条件的计数各加1

2。用行2去比行3，行4，行5。符合条件的计数各加1

3。类推....


1。 1234567890 2 5 计为 2
2。 1234567800 1 5 计为 2
3。 3456789012 计为 0
4。 3456789456 计为 0
5。 1234567877 1 2 计为 2

[此贴子已经被作者于2005-10-31 20:56:52编辑过]

采用上述算法，非常适合使用多线程,你完全可起足够多的线程从不同的起点开起对比。十几秒不说，按你的算法单线程只要30分钟，我的算法对比量又少了一半，也就是15分钟，如果起几个线程，1，2分钟应足够了吧?

你这个算法我还是不大明白，

1。 1234567890 2 5 计为 2
2。 1234567800 1 5 计为 2
3。 3456789012 计为 0
4。 3456789456 计为 0
5。 1234567877 1 2 计为 2

如果1。为1234567891的话，那么2。就有2个8个字符相同的，它们是1234567890和1234567877。可是1234567890没计算进去。只比较后面的话，前面有互异的不就漏掉了吗？还有红色部分的5、5、2是什么意思？

忘了说明一下，比较是按位进行的，1234567891和1234567800是2互异，3456789012和1234567890是10互异。

[此贴子已经被作者于2005-11-1 0:18:07编辑过]

对于第n行来说只比较n+1.......100万行，那么前面1....n-1行怎么办，关键是我不理解如何把前面比较过的结果记在n行上。难道是构造一个含100万个元素的数组来记录？有点明白了，我要仔细再想一想。

[此贴子已经被作者于2005-11-1 0:33:45编辑过]

还是没想明白如何把前面比较过的结果记在n行上，斑竹再指点下

这个i很大么？你的程序很占内存么？用数组来记录也行，数值达到i的大小就不必累计了。