如何在不触发 Out of Local Stack 异常的情况下计算两个大字符串的每个字符的巧合？

Question

我需要一个子句来计算两个大字符串之间的字符巧合但忽略'_'巧合。我有这个代码：

fit(GEN1, GEN2, N, N) :-
   length(GEN1, L1),
   length(GEN2, L2),
   0 is L1*L2.

fit([P1|R1], [P2|R2], N, TOTAL) :-
   member(P1, ['_',a,c,t,g]),
   member(P2, ['_',a,c,t,g]),
   append([P1],[P2],T),
   (  member(T,[[a,a],[c,c],[t,t],[g,g]])
   -> X is N+1
   ;  X is N
   ),
   fit(R1,R2,X,TOTAL).

WhereGEN1和GEN2are 包含所有字符大字符串的列表。

我尝试增加堆栈限制以避免Out of Local Stack异常，但收效甚微。

问题是，在深度递归子句中经常被调用。有没有更好的方法来做到这一点？

编辑

当一个或两个列表为空时，该子句需要停止。

编辑 2

值得一提的是，以下所有答案的测试都是使用 64 位序言完成的，该--stack-limit=32g选项是因为我的代码没有得到很好的优化，并且该fit子句是较大过程的一小部分，但它是我的代码的主要问题。

编辑 3

CapelliC 代码使用较少的资源工作。

使用library(reif)v2 的假代码工作得更快。

有关更多建议的解决方案，请参阅计算两个序列中匹配元素的复杂性library(aggregate)。

Answer 1

似乎没有必要坚持你一直都有信件"_actg"。一个广义的定义似乎就足够了。使用library(reif)：

fit([], _, N,N).
fit([_|_], [], N,N).
fit([P1|R1], [P2|R2], N,TOTAL) :-
   if_( ( P1 = P2, dif(P1, '_') ), X is N+1, X = N ),
   fit(R1, R2, X,TOTAL).

更新：请确保使用 v2 of library(reif). 原始版本没有编译dif/3。

这是一个只能同时索引一个参数的系统版本：

fit([], _, N,N).
fit([P1|R1], L2, N,TOTAL) :-
    ifit(L2, [P1|R1], N,TOTAL).

ifit([], _, N,N).
ifit([P2|R2], [P1|R1], N,TOTAL) :-
   if_( ( P1 = P2, dif(P1, '_') ), X is N+1, X = N ),
   fit(R1, R2, X,TOTAL).