大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > Java实现字符串的匹配

Java实现字符串的匹配

关键词:Java字符串匹配Java实现字符串的匹配  阅读(681) 赞(18)

[摘要]本文主要是对Java实现字符串的匹配的讲解,希望对大家学习Java实现字符串的匹配有所帮助。

  假设我们有一个一定个数的字母组成字串,我给每个字母分配一个素数,从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");

  }

  }

  }

  }



相关评论