Java实现字符串的匹配

假设我们有一个一定个数的字母组成字串，我给每个字母分配一个素数，从2开始，往后类推。这样A将会是2，B将会是3，C将会是5，等等。现在我遍历第一个字串，把每个字母代表的素数相乘。你最终会得到一个很大的整数，对吧？

　　然后——轮询第二个字符串，用每个字母除它。如果除的结果有余数，这说明有不匹配的字母。如果整个过程中没有余数，你应该知道它是第一个字串恰好的子集了。

　　思路总结如下：

　　1.定义最小的26个素数分别与字符'A'到'Z'对应。

　　2.遍历长字符串，求得每个字符对应素数的乘积。

　　3.遍历短字符串，判断乘积能否被短字符串中的字符对应的素数整除。

　　4.输出结果。

　　至此，如上所述，上述算法的时间复杂度为O(m+n)，时间复杂度最好的情况为O(n)

package contcurrentandalgorithm;
/**
*
* @author Administrator
* [e-mail]
*/
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");
    }
  }
 }
}

 

评论

5 楼 jonas.wang 2013-11-29  

这个本身只是判断字符串1 是否包含 字符串2 的字符。
且判断的if条件还需要改进下。

4 楼 hcc609567014 2013-11-28  

让我重新学习了素数的特性。。。

3 楼 leaow567 2013-11-28  

可惜有硬伤啊
1）java大数据运算，你这代码里面没处理
2）逻辑上也有错误，判断是否到数组末尾出错
3）数学理论上，这个算法只能判断父串是否含有子串的字符，没有前后顺序的机制
。。。。
我认真了。。。。。

2 楼 hellohank 2013-11-28  

这个想法很独特，巧妙运用了素数的特性，这种创造性的思维值得推崇，但这个算法有个缺陷（先不说如果字符串较长时运算的数字大小问题）：下面这对字符串它也会判定是true的：
strOne=ABCDEFGH
strTwo=ABCDH

我想你应该能看出问题在哪儿了~

1 楼 leaow567 2013-11-28  

茅塞顿开啊~~