有一道编程趣题,

要求判断一段文字T中,是否包含一个字符串W的某种排列。

据说不少公司还用这道题目用来面试程序员。题目的答案在网络上也到处都能搜索到。这道题目存在一个特别优雅的解法,体现了数学同构的优美。

数论中的算术基本定理说:任何一个正整数都可以唯一地表示成若干素数的乘积。我们的思路是,将每一个不同字符对应到一个素数上去,a对应2,b对应 3,c对应5......。这样任意给定一个字符串W,不管它是否包含重复的字符,我们都可以把它表示为素数的乘积:

F = product([primes[c] for c in W]])

我们称其为字符串W的数论指纹F。如果W是空串,我们规定它的指纹等于1。根据整数乘法的交换律,我们知道无论W怎样排列,其数论指纹都不变,并且根据算术基本定理,这个数论指纹是唯一的。现在我们就得到 了一个特别简洁的解法:我们首先计算出W的数论指纹F ,然后用一个长度为|W|的窗口沿着TXT从左向右滑动。一开始我们需要计算TXT在这个窗口内的数论指纹,并和F比较,如果相等就说明TXT包含W的某种排列。如果不等我们将这个窗口向右滑动一个字符。此时我们可以非常容易地计算新窗口内的数论指纹:只要把滑出的字符对应的素数除掉,再把滑入的字符对应的素数乘上就可以了。任何时候如果新窗口内的数论指纹等于F,就说明找到了一个排列。当然为了获得每个不同字符对应的素数,我们还要利用埃拉托斯特尼筛法产生一串素数。下面是一个例子Java程序:

import java.util.stream.LongStream;
import java.util.function.LongPredicate;

public class PermuteSubstr {
    private static final int ASCII = 128;
    private static LongPredicate sieves = x -> true; // initialize sieve as id
    private final static long[] PRIMES = LongStream
        .iterate(2, i -> i + 1)
        .filter(i -> sieves.test(i))  // Sieve of Eratosthenes
        .peek(i -> sieves = sieves.and(v -> v % i != 0)) // update, chain the sieve
        .limit(ASCII)                 // only support ASCII
        .toArray();

    private static long product(String str) {
        return str.chars().mapToLong(c -> PRIMES[c]).reduce(1, (a, b) -> a * b);
    }

    public static boolean exist(String w, String txt) {
        if (w.isEmpty()) {
            return true;
        }
        int m = w.length(), n = txt.length();
        if (n < m) {
            return false;
        }
        long target = product(w);
        long fp = product(txt.substring(0, m));
        for (int i = m; i < n && target != fp; ++i) {
            fp = fp / PRIMES[txt.charAt(i - m)] * PRIMES[txt.charAt(i)];
        }
        return target == fp;
    }
}

这段程序中素数序列的产生也很有趣,它利用了埃拉托斯特尼筛法,使用了无穷流的概念,并截取了前128个素数以处理所有的ASCII码。关于无穷流可以参见《同构——编程中的数学》中“无穷”一章。有关算术基本定理的证明也是数学中优美证明的经典,大数学家柯朗和罗宾的科普读物《什么是数学》中有详细的介绍。