假设我们有一个一定个数的字母组成字串，我给每个字母分配一个素数，从2开始，往后类推。这样A将会是2，B将会是3，C将会是5，等等。现在我遍历第一个字串，把每个字母代表的素数相乘。你最终会得到一个很大的整数，对吧？
然后——轮询第二个字符串，用每个字母除它。如果除的结果有余数，这说明有不匹配的字母。如果整个过程中没有余数，你应该知道它是第一个字串恰好的子集了。
思路总结如下：
1.定义最小的26个素数分别与字符'A'到'Z'对应。
2.遍历长字符串，求得每个字符对应素数的乘积。
3.遍历短字符串，判断乘积能否被短字符串中的字符对应的素数整除。
4.输出结果。
至此，如上所述，上述算法的时间复杂度为O(m+n)，时间复杂度最好的情况为O(n)
package contcurrentandalgorithm; /** * * @author Administrator * zyyjiao@mail.ustc.edu.cn */ public class SushuStringFind { public static void main(String[] args) { int primeNumber[] = {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}; String strOne = "ABCDEFGHLMNOPQRS"; String strTwo = "ABCDEFGHL"; // 这里需要用到大整数 int product = 1; //大整数除法的代码，下头给出。 // 遍历长字符串，得到每个字符对应素数的乘积 for (int i = 0; i < strOne.length(); i++) { int index = strOne.charAt(i) - 'A'; product = product * primeNumber[index]; } // 遍历短字符串 for (int j = 0; j < strTwo.length(); j++) { int index = strTwo.charAt(j) - 'A'; // 如果余数不为0，说明不包括短字串中的字符，跳出循环 if (product % primeNumber[index] != 0) { break; } if (strTwo.length() == j) //cout << "true" << endl; { System.out.println("true"); } else //cout << "false" << endl; { System.out.println("false"); } } } } |
