string - 导出字符串替换

Question

在很多语言中，都有一个函数可以做这样的事情:

replace(string, pattern, replacement)
replace("aSb", "S", "ba")
  => "abab"

但是有什么方法可以编写一个相反的函数吗？

derive_replacement(before_string, after_string)
derive_replacement("space ba ba space ba", "fact ba ba fact ba")
  => ("space", "fact")

我知道有几种方法可以返回一条规则，让您从一个字符串到另一个字符串，但我正在寻找最短的方法。例如，以下两种方法在技术上都可行，但不会找到最短的字符串:

derive(before, after) {
    return (before, after)
}

derive(before, after) {
    first_diff = len(commonprefix(before, after))
    last_diff = len(commonsuffix(before, after))
    return (before[first_diff:len(before) - last_diff],
        after[first_diff:len(after) - last_diff])
}

我正在寻找一种通用的方法来执行此操作，但如果它有帮助，我正在尝试让它在 Haskell 中工作。不过，任何语言甚至伪代码都足够了。

Answer 1

这不是一个简单的问题。

在某些情况下，您的第二个示例会提供错误的结果。想想如果你打电话会发生什么

派生(“foo foo foo”，“foo baz foo”)。

显然，蛮力方法是可能的，例如(在类似 C 的伪代码中)

if (before==after) return "",""
for (pl=1;pl<(len(before)-1);pl++) {
  for (ps=0;ps<=len(before)-pl;ps++) {
    for (rl=1;rl<len(after)-ps;rl++) {
      pattern=substr(before,ps,pl);
      replacement=substr(after,ps,rl);
      if (replace(before,pattern,replacement) == after) {
        return(pattern,replacement);
      }
    }
  }
}
return (before,after);

不知道有没有更高效的解决方案。