Heaven wrote:
> 
> Shann 兄:
> 
> > 这就是所谓 pattern matching 的想法.  我不清楚您的程式依据什麽算法写的.
> > 请找一本资料结构或演算法则的课本, 找一个称做 Knuth-Morris-Pratt 的算法.
> 
>   昨天翻了一下家中的书 :) , 果然有看到这个演算法, 但和以前一样, 还是看不懂
> :<
> 
>   不过, 那个是在一个长字串中找某一段短字串的技巧, 其实这方面我直接用 c 的函
>   数就搞定了.
> 
>   後学的重点在於, 在二个长字串中, 如何判断那些部份是相同的,
> 那些部份是不同的,
>   我想大家都懂我的意思, 不过还是举例一下:
> 
>   我爱大自然, 喜欢大自然, 您爱不爱?
>   我爱太白然, 喜欢大自然, 您爱不爱?
> 
>   写的不好的程式, 有时会看成 (我的程式就会啦!)
> 
>   我爱　　　　　　大自然....
>   我爱太白然，喜欢大自然....
> 
>   这些判断如何叫电脑做呢? 有什麽好规则?
> 
>   Heaven
可以考虑用辞库来作辅助.

--
------------------------------------------------------------------------
张文明
日月工作室
voice: 886-2-658-0270 (night)
mailto: dnstudio@m2.dj.net.tw 或 wmc@mozart.seed.net.tw
电子佛教藏经阁: http://w5.dj.net.tw/~DNStudio/canon 或
http://www.tyba.org.tw/canon

> >   我爱大自然, 喜欢大自然, 您爱不爱?
> >   我爱太白然, 喜欢大自然, 您爱不爱?
> >   写的不好的程式, 有时会看成 (我的程式就会啦!)
> >   A.我爱　　　　　　大自然....
> >   B.我爱太白然，喜欢大自然....
> >   这些判断如何叫电脑做呢? 有什麽好规则?

>     再多加个判断, 将 B.中的「太白然，喜欢」当成另一列待判断的字串, 而将
>   A.中「大自」之後的「然，喜欢大自然...」与上述的「太白然，喜欢」做比较.
>     这样或许可以解决此类问题. 

  能否说详细一些, 後学不是很能弄清您的建议...

  另外, 举个黄金□例, 供大家动脑

　１２３４５６ＡＢ３４甲乙ＥＦＧ
　甲乙丙丁ＡＢ３４甲乙ＥＦＧ

标准答案：
　１２３４５６ＡＢ３４甲乙ＥＦＧ
　甲乙丙丁　　ＡＢ３４甲乙ＥＦＧ

错误１：(第一行找到二个相同的就对到第二行去)
　１２　　　　３４５６ＡＢ３４甲乙ＥＦＧ
　甲乙丙丁ＡＢ３４　　　　　　甲乙ＥＦＧ

错误２：(第二行找到二个相同的就对到第一行去)
　１２３４５６ＡＢ３４甲乙　　　　　　　　ＥＦＧ
　　　　　　　　　　　甲乙丙丁ＡＢ３４甲乙ＥＦＧ

您如何要电脑去判断上面的逻辑呢?

  Heaven

Heaven wrote:
> 
>   另外, 举个黄金□例, 供大家动脑
> 
> 　１２３４５６ＡＢ３４甲乙ＥＦＧ
> 　甲乙丙丁ＡＢ３４甲乙ＥＦＧ
> 
> 标准答案：
> 　１２３４５６ＡＢ３４甲乙ＥＦＧ
> 　甲乙丙丁　　ＡＢ３４甲乙ＥＦＧ
> 
> 错误１：(第一行找到二个相同的就对到第二行去)
> 　１２　　　　３４５６ＡＢ３４甲乙ＥＦＧ
> 　甲乙丙丁ＡＢ３４　　　　　　甲乙ＥＦＧ
> 
> 错误２：(第二行找到二个相同的就对到第一行去)
> 　１２３４５６ＡＢ３４甲乙　　　　　　　　ＥＦＧ
> 　　　　　　　　　　　甲乙丙丁ＡＢ３４甲乙ＥＦ□gt; 
>
> 您如何要电脑去判断上面的逻辑呢?

好！让我这个不懂程式、不懂数学的人再来乱想一通，或
许可以激发大家的灵感。

先把这个黄金□例修改成这样：
□□□□□□□□□□□□□□□□□□□□□□□□□
字序  01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
－－－－－－－－－－－－－－－－－－－－－－－－－
Ａ档　１ ２ ３ ４ ５ ６ Ａ Ｂ ３ ４ 甲 乙 Ｅ Ｆ Ｇ
Ｂ档　甲 乙 丙 丁 Ａ Ｂ ３ ４ 甲 乙 Ｅ Ｆ Ｇ
□□□□□□□□□□□□□□□□□□□□□□□□□

假设每次从Ａ档抓一个字来跟Ｂ档比，且每次都从Ｂ档的
开头第一个字比起。

Ａ档第01个字「１」在Ｂ档找不到，记录值∞。
Ａ档第02个字「２」在Ｂ档找不到，记录值∞。
Ａ档第03个字「３」在Ｂ档07找到，记录值 7。
Ａ档第04个字「４」在Ｂ档08找到，记录值 8。
Ａ档第05个字「５」在Ｂ档找不到，记录值∞。
Ａ档第06个字「６」在Ｂ档找不到，记录值∞。
Ａ档第07个字「Ａ」在Ｂ档05找到，记录值 5。
Ａ档第08个字「Ｂ」在Ｂ档06找到，记录值 6。
Ａ档第09个字「３」在Ｂ档07找到，记录值 7。
Ａ档第10个字「４」在Ｂ档08找到，记录值 8。
Ａ档第11个字「甲」在Ｂ档01、09找到，记录值 1、 9。
Ａ档第12个字「乙」在Ｂ档02、10找到，记录值 2、10。
Ａ档第13个字「Ｅ」在Ｂ档11找到，记录值11。
Ａ档第14个字「Ｆ」在Ｂ档12找到，记录值12。
Ａ档第15个字「Ｇ」在Ｂ档13找到，记录值13。

从上面的观察，当Ａ档第11、12字各产生两个记录值时，依据前
後连续性来考量，应当取记录值9跟10。

很显然的，Ａ档第03、04字有连续记录值7、8，其记录值总和为
7+8=15。但Ａ档从第07到15字皆有连续记录值，且当中亦包含记
录值7、8，而其开始连续的头两个（第07、08字）记录值总和为
5+6=11。

若考虑这两个发生连续记录值的区段，第二个区段的□围不但大
於第一个区段，而且包含第一个区段，所以应当放弃第一个区段。

再从记录值总和来看，第一个区段的两个记录值总和为7+8=15，
第二个区段头两个记录值总和为 5+6=11，因为15>11，所以应该
放弃第一个区段。

□□□□□□□□□□□□□□□□□
 摩诃工作室．吴宝原
 E-mail:maha@tpts1.seed.net.tw
 Tel:(02)6741715/Fax:(02)6741716
□□□□□□□□□□□□□□□□□

Heaven wrote:
> 
>   另外, 举个黄金□例, 供大家动脑
> 
> 　１２３４５６ＡＢ３４甲乙ＥＦＧ
> 　甲乙丙丁ＡＢ３４甲乙ＥＦＧ
> 
> 标准答案：
> 　１２３４５６ＡＢ３４甲乙ＥＦＧ
> 　甲乙丙丁　　ＡＢ３４甲乙ＥＦＧ
> 
> 错误１：(第一行找到二个相同的就对到第二行去)
> 　１２　　　　３４５６ＡＢ３４甲乙ＥＦＧ
> 　甲乙丙丁ＡＢ３４　　　　　　甲乙ＥＦＧ
> 
> 错误２：(第二行找到二个相同的就对到第一行去)
> 　１２３４５６ＡＢ３４甲乙　　　　　　　　ＥＦＧ
> 　　　　　　　　　　　甲乙丙丁ＡＢ３４甲乙ＥＦ□gt; 
>
> 您如何要电脑去判断上面的逻辑呢?

好！让我这个不懂程式、不懂数学的人再来乱想一通，或
许可以激发大家的灵感。

先把这个黄金□例修改成这样：
□□□□□□□□□□□□□□□□□□□□□□□□□
字序  01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
－－－－－－－－－－－－－－－－－－－－－－－－－
Ａ档　１ ２ ３ ４ ５ ６ Ａ Ｂ ３ ４ 甲 乙 Ｅ Ｆ Ｇ
Ｂ档　甲 乙 丙 丁 Ａ Ｂ ３ ４ 甲 乙 Ｅ Ｆ Ｇ
□□□□□□□□□□□□□□□□□□□□□□□□□

假设每次从Ａ档抓一个字来跟Ｂ档比，且每次都从Ｂ档的
开头第一个字比起。

Ａ档第01个字「１」在Ｂ档找不到，记录值∞。
Ａ档第02个字「２」在Ｂ档找不到，记录值∞。
Ａ档第03个字「３」在Ｂ档07找到，记录值 7。
Ａ档第04个字「４」在Ｂ档08找到，记录值 8。
Ａ档第05个字「５」在Ｂ档找不到，记录值∞。
Ａ档第06个字「６」在Ｂ档找不到，记录值∞。
Ａ档第07个字「Ａ」在Ｂ档05找到，记录值 5。
Ａ档第08个字「Ｂ」在Ｂ档06找到，记录值 6。
Ａ档第09个字「３」在Ｂ档07找到，记录值 7。
Ａ档第10个字「４」在Ｂ档08找到，记录值 8。
Ａ档第11个字「甲」在Ｂ档01、09找到，记录值 1、 9。
Ａ档第12个字「乙」在Ｂ档02、10找到，记录值 2、10。
Ａ档第13个字「Ｅ」在Ｂ档11找到，记录值11。
Ａ档第14个字「Ｆ」在Ｂ档12找到，记录值12。
Ａ档第15个字「Ｇ」在Ｂ档13找到，记录值13。

从上面的观察，当Ａ档第11、12字各产生两个记录值时，依据前
後连续性来考量，应当取记录值9跟10。

很显然的，Ａ档第03、04字有连续记录值7、8，其记录值总和为
7+8=15。但Ａ档从第07到15字皆有连续记录值，且当中亦包含记
录值7、8，而其开始连续的头两个（第07、08字）记录值总和为
5+6=11。

若考虑这两个发生连续记录值的区段，第二个区段的□围不但大
於第一个区段，而且包含第一个区段，所以应当放弃第一个区段。

再从记录值总和来看，第一个区段的两个记录值总和为7+8=15，
第二个区段头两个记录值总和为 5+6=11，因为15>11，所以应该
放弃第一个区段。

□□□□□□□□□□□□□□□□□
 摩诃工作室．吴宝原
 E-mail:maha@tpts1.seed.net.tw
 Tel:(02)6741715/Fax:(02)6741716
□□□□□□□□□□□□□□□□□

> >   我爱大自然, 喜欢大自然, 您爱不爱?
> >   我爱太白然, 喜欢大自然, 您爱不爱?
> >   写的不好的程式, 有时会看成 (我的程式就会啦!)
> >   A.我爱　　　　　　大自然....
> >   B.我爱太白然，喜欢大自然....
> >   这些判断如何叫电脑做呢? 有什麽好规则?

>     再多加个判断, 将 B.中的「太白然，喜欢」当成另一列待判断的字串, 而将
>   A.中「大自」之後的「然，喜欢大自然...」与上述的「太白然，喜欢」做比较.
>     这样或许可以解决此类问题. 

  能否说详细一些, 後学不是很能弄清您的建议...

  另外, 举个黄金□例, 供大家动脑

　１２３４５６ＡＢ３４甲乙ＥＦＧ
　甲乙丙丁ＡＢ３４甲乙ＥＦＧ

标准答案：
　１２３４５６ＡＢ３４甲乙ＥＦＧ
　甲乙丙丁　　ＡＢ３４甲乙ＥＦＧ

错误１：(第一行找到二个相同的就对到第二行去)
　１２　　　　３４５６ＡＢ３４甲乙ＥＦＧ
　甲乙丙丁ＡＢ３４　　　　　　甲乙ＥＦＧ

错误２：(第二行找到二个相同的就对到第一行去)
　１２３４５６ＡＢ３４甲乙　　　　　　　　ＥＦＧ
　　　　　　　　　　　甲乙丙丁ＡＢ３４甲乙ＥＦＧ

您如何要电脑去判断上面的逻辑呢?

  Heaven

==> 於  ("Heaven") 文中述及:
:   能否说详细一些, 後学不是很能弄清您的建议...
:   另外, 举个黄金□例, 供大家动脑
: 　１２３４５６ＡＢ３４甲乙ＥＦＧ
: 　甲乙丙丁ＡＢ３４甲乙ＥＦＧ
: 标准答案：
: 　１２３４５６ＡＢ３４甲乙ＥＦＧ
: 　甲乙丙丁　　ＡＢ３４甲乙ＥＦＧ
: 错误１：(第一行找到二个相同的就对到第二行去)
: 　１２　　　　３４５６ＡＢ３４甲乙ＥＦＧ
: 　甲乙丙丁ＡＢ３４　　　　　　甲乙ＥＦＧ
: 错误２：(第二行找到二个相同的就对到第一行去)
: 　１２３４５６ＡＢ３４甲乙　　　　　　　　ＥＦＧ
: 　　　　　　　　　　　甲乙丙丁ＡＢ３４甲乙ＥＦＧ
: 您如何要电脑去判断上面的逻辑呢?

小弟有找到两篇探讨这类问题的文章, 供师兄参考:
[1] "A File Comparison Program", by Webb Miller & Eugene W. Myers, from
    SOFTWARE-PRACTICE AND EXPERIENCE, VOL. 15(11), 1025-1040(NOVEMBER 1985)

[2] "An O(ND) Difference Algorithm and Its Variations" by Eugene W. Myers,
    from ALGORITHMICA (1986) VOL.1 pp.251-266

如果你在图书馆找不到的话, 小弟可以寄一分给你,
或是等小弟期末考完, k 他一 k, 再POST上来 ^_^