有一道编程趣题,
要求判断一段文字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码。关于无穷流可以参见《同构——编程中的数学》中“无穷”一章。有关算术基本定理的证明也是数学中优美证明的经典,大数学家柯朗和罗宾的科普读物《什么是数学》中有详细的介绍。
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239,
直接给出不好吗?
return PRIMES[c - 'a'];
}
不需要考虑大小写字母吗,在 Java 中 a-zA-Z 似乎不是连续编码的。
建议改为:
return (c >= 'a' && c <= 'z') ? PRIMES[c - 'a'] : (c >= 'A' && c <= 'Z') ? PRIMES[c - 'A'] : 0;
或
return Character.isLowerCase(c) ? PRIMES[c - 'a'] : Character.isUpperCase(c) ? PRIMES[c - 'A'] : 0;