求两字符串最大顺序匹配数

aimisiyou

两字符串，如str1="horse",str2="sayhello",结果为2。(若前面选"h"和"o"，后面同顺序可选"h"和"o"；若前面选择"s"和"e",后面可选"s"和"e"。)

aimisiyou

如果str1内没有重复的字符，很好算。如str1="abcde",str2="excbade"，可以将str1中每个字符对应1，2，3，4，5，
则str2中每个字符对应str1中的位置为5，0，3，2，1，4，5，（其中0表示不存在对应位置），然后统计每个非0数字后大于该数的个数，即5后面有0个大于5的数，3后面有2个大于3的数，2后面有2个大于2的数，1后面有2个大于1的数，4后面有1个大于4的数，故max{0+1，2+1，2+1，2+1，1+1}=3

aimisiyou

_$ (setq str "abcde")
(setq n (strlen str))
(setq i 1 strlst nil)
(while (<= i n)
   (setq j 1 )
   (while (<= j (- n i -1))
      (setq strlst (cons (substr str i j) strlst))
          (setq j (+ j 1))
   )
   (setq i (+ i 1))
)
(reverse strlst)
"abcde"
5
nil
6
("a" "ab" "abc" "abcd" "abcde" "b" "bc" "bcd" "bcde" "c" "cd" "cde" "d" "de" "e")
_$ (setq str "abcde")
(setq n (strlen str))
(defun f (num)(setq k num plst nil)(while (> k 0)(setq k (- k 1))(setq plst (cons k plst))))
(mapcar '(lambda (nn) (cons (- (lsh 1 nn) 1) (mapcar '(lambda (x) (lsh (boole 6 (lsh (- (lsh 1 nn) 1) (* -1 x)) 1) x))  (f (- nn 1))))) (reverse (cdr (f (+ 1 n)))))
"abcde"
5
F
((31 30 28 24 16) (15 14 12 8) (7 6 4) (3 2) (1))
_$

aimisiyou

如果str1中有重复字符，就复杂些。如str1="intention",str2="execution"。结果应为5。

aimisiyou

按照字符不重复的思路，若有重复，str2中每个字符对应str1中的位置可能有多个，如str1="intention",str2="execution，str1={（1，"i"）（2，"n"）（3，"t"）（4，"e"）（5，"n"）（6，"t"）（7，"i"）（8，"o"）（9，"n"）}。str2中每个字符对应的位置可能是4，0，4，0，0，（3，6），（1，7），8，（2，5，9）。剩下的问题是如何选取重复位置，使得整体顺序数个数达到最大？所以，选取4，0，4，0，0，6，7，8，9得到最大顺序数个数5。

aimisiyou

若按暴力穷举的方法，要将重复位置个数相乘，不是好办法。

tzfcn

有好的创意并能够实现，是一种快乐！

aimisiyou

问题转化为X1有n1种选择，X2有n2种选择，X3有n3种选择，……Xk有nk种选择，如何选择构成的（X1，X2，X3，……Xk）递增顺序数个数最多？

zhystar

自问自答，谢谢分享

aimisiyou

aimisiyou 发表于 2020-2-21 23:03
问题转化为X1有n1种选择，X2有n2种选择，X3有n3种选择，……Xk有nk种选择，如何选择构成的（X1，X2，X3，… ...

曼哈顿距离。复杂度O(n).