返回信息流代码如下：static size_t
lcs( struct text *txt0,
size_t i0, /* input: starting position */
struct text **tbp, /* output: position of best run */
size_t *ibp,
size_t i_first, /* no comparison before this pos. */
size_t i_limit /* no comparison after this pos. */
) {
/* Finds the longest common substring (not subsequence) in:
txt0, starting precisely at i0 and
the text from i_first to i_limit-1.
Writes the position in tbp and ibp and returns the size.
Returns 0 if no common substring is found.
*/
struct text *txt1 = txt0;
size_t i1 = i0;
size_t size_best = 0;
while ( /* there is a next opportunity */
(i1 = Forward_Reference(i1)) //hash.c
&& /* it is still in range */
i1 < i_limit
) {
size_t min_size= (size_best ? size_best+1 : Min_Run_Size);
if (i1 < i_first) { /* not in range */
continue;
}
/* bump txt1; we may have to skip a text or two */
while (i1 >= txt1->tx_limit) {
txt1++;
}
/* are we looking at something better than we have got? */
{ /* comparing backwards */
size_t j0 = i0 + min_size - 1;
size_t j1 = i1 + min_size - 1;
if ( /* j0 still inside txt0 */
j0 < txt0->tx_limit
&& /* j1 still inside txt1 */
j1 < txt1->tx_limit
&& /* j0 and j1 don't overlap */
j0 + min_size <= j1
) {
/* there is room enough for a match */
size_t cnt = min_size;
/* text matches for at least min_size tokens? */
while ( cnt
&& Token_EQ(Token_Array[j0],
Token_Array[j1])
) {
cnt--, j0--, j1--;
}
if (cnt) continue; /* forget it */
}
else continue; /* forget it */
}
/* yes, we are; how long can we make it? */
size_t new_size = min_size;
{ /* extending forwards */
size_t j0 = i0 + min_size;
size_t j1 = i1 + min_size;
while ( /* j0 still inside txt0 */
j0 < txt0->tx_limit
&& /* j1 still inside txt1 */
j1 < txt1->tx_limit
&& /* j0 and j1 don't overlap */
j0 + new_size < j1
&& /* tokens are the same */
Token_EQ(Token_Array[j0], Token_Array[j1])
) {
j0++, j1++, new_size++;
}
}
/* offer the run to the Language Department which may
reject it or may cut its tail
*/
new_size = ( May_Be_Start_Of_Run(Token_Array[i0]) //algollike.c May_Be_Start_Of_Algol_Run
? Best_Run_Size(&Token_Array[i0], new_size) //algollike.c Best_Algol_Run_Size
: 0
);
if ( /* we still have something acceptable */
new_size >= Min_Run_Size
&& /* it is better still than what we had */
new_size > size_best
) {
/* record it */
*tbp = txt1;
*ibp = i1;
size_best = new_size;
}
}
return size_best;
}
问题：理论上应该求出两个输入文件的最大公共子串，可是这句struct text *txt1 = txt0; 让我始终只能看到一个输入文件，即函数被调用时传进来的txt0 理解不通，大牛给点播一下，还是代码写的有问题？
这是一条镜像帖。来源：北邮人论坛 / cpp / #91742同步于 2016/5/19
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
请教：lcs算法中一个变量声明的问题
mandy4321
2016/5/19镜像同步2 回复
订阅后，新回复会通过你的通知中心匿名送达。
2 条回复
/* Finds the longest common substring (not subsequence) in:
txt0, starting precisely at i0 and
the text from i_first to i_limit-1.
Writes the position in tbp and ibp and returns the size.
Returns 0 if no common substring is found.
*/
注释不是说了
Finds the longest common substring (not subsequence) in:
txt0, starting precisely at i0 and
the text from i_first to i_limit-1.
不就是在 txt0 的两个范围内找吗？
嗯，看明白了。之前有一个顽固思维“必须是‘两个’输入文件才可有最长公共子串”，一直没跳出来
【 在 Vampire 的大作中提到: 】
: /* Finds the longest common substring (not subsequence) in:
: txt0, starting precisely at i0 and
: the text from i_first to i_limit-1.
: ...................