clojurescript - 如何在不使用任何内置函数的情况下用另一个子字符串替换主输入字符串中的子字符串？

Question

我在网上搜索的每个函数都利用任何一个内置函数，如 find()、replace().etc 。我在学术书籍、图书馆和互联网上进行了研究，但找不到解决方案。你们中的任何人都可以提供一种在不使用任何内置函数的情况下实现上述功能的算法吗？

Answer 1

好吧，让我们先尝试解决一些更简单的问题，然后逐步解决字符串替换问题。首先，我们如何判断两个字符串相等？相当简单，对吧？如果字符串长度相同，并且相同字符的顺序相同，则它们相等:

(defn str-eq? [s1 s2]
  (and (= (count s1) (count s2))
       (every? identity
               (map = s1 s2))))

好吧，让我们尝试检查一个字符串是否有其他字符串作为前缀。事实证明，这是一个几乎相同的解决方案，我们只是放宽了两个字符串长度相同的要求:

(defn str-prefix? [s prefix]
  (and (>= (count s) (count prefix))
       (every? identity
               (map = s prefix))))

现在，让我们开始思考如何找到某个字符串 s 中所有出现的某个字符串 s1。好吧，如果我们将 s 的所有后缀按照从最长到最短的顺序排列，我们可以通过检查哪些后缀 s1 是以下前缀来确定 s1 出现在 s 中的位置:

(defn str-suffixes [s]
  (->> s
       (iterate next)
       (take (inc (count s))) ;; make sure we include the empty string
       (map #(apply clojure.core/str %))))

(defn str-find [s s1]
  (->> (str-suffixes s)
       (map (fn [index suffix] 
              (if (str-prefix? suffix s1) 
                index 
                nil))
            (iterate inc 0))
       (filter identity)))

最后，是时候进行字符串替换了。我们将从简单的情况开始，其中字符串 s1 在字符串 s 的索引处最多出现一次。只需将索引之前的所有内容与替换字符串 s2 以及 s 中出现 s1 之后的所有内容连接起来即可:

(defn str-replace [s s1 s2]
  (reduce (fn [s index]
            (apply clojure.core/str 
                   (concat (take index s)
                           s2
                           (drop (+ index (count s1)) s))))
          s
          (str-find s s1)))

如果s1在s中出现多次，你会发现这不起作用。这是因为 str-find 按升序给出结果。每次进行字符串替换时，都会使字符串中后面的索引失效。为了解决这个问题，我们只需从最大到最小处理每个索引:

(defn str-replace [s s1 s2]
  (reduce (fn [s index]
            (apply clojure.core/str 
                   (concat (take index s)
                           s2
                           (drop (+ index (count s1)) s))))
          s
          (sort > (str-find s s1))))

它正在发挥作用:

(str-replace "foobar" "foo" "baz")
=> "bazbar"
(str-replace "foobar" "bar" "baz")
=> "foobaz"
(str-replace "foobarbarfoo" "bar" "bazz")
=> "foobazzbazzfoo"
(str-replace "foobar" "z" "baz")
=> "foobar"

在解决此类问题时，思考还有哪些其他类似的操作以及它们与您要实现的操作之间的关系会有所帮助。如果您有任何疑问，请告诉我。