假设我们有一个一定个数的字母组成字串,我给每个字母分配一个素数,从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"); } } } }
相关推荐
本文介绍了如何使用 Java 实现字符串匹配,并且提供了基于素数乘积的算法实现。该算法的时间复杂度为 O(m+n),可以有效地实现字符串匹配操作。在实际应用中,可以根据需要选择合适的算法和数据结构来实现字符串匹配...
在Java编程中,实现字符串匹配并寻找两个字符串的最大公共子串是一项常见的任务,尤其是在文本处理、数据比较和信息检索等领域。本示例介绍了一种基于二维数组(也称为动态规划矩阵)的算法来解决这个问题。 最大...
Boyer-Moore法实现字符串匹配(java) 在字符串匹配问题中,Boyer-Moore算法是一种高效的解决方案。该算法使用坏字符移动表和好后缀移动表来实现字符串匹配。下面将详细解释Boyer-Moore算法的实现原理和java代码...
通过以上知识点,我们可以高效地在Java中实现字符串匹配、查找、替换等操作,处理各种复杂的文本处理任务。对于需要频繁处理字符串的程序,熟练掌握正则表达式和Java的`java.util.regex` 包是非常有益的。
总的来说,Java字符串匹配是一个基础但重要的编程概念,可以采用多种策略来实现,每种策略都有其适用的场景和优缺点。理解这些方法可以帮助开发者在实际项目中做出合适的选择。如果你对编程感兴趣,尤其是Java语言,...
这里主要讨论的是KMP(Knuth-Morris-Pratt)算法,这是一种高效的字符串匹配算法,适用于在主字符串中查找目标子串是否存在。 KMP算法的核心在于构建一个“部分匹配表”(next function),它存储了目标子串的前缀...
总结,Java中的字符串分割是通过`split()`方法实现的,依赖于正则表达式进行精确的分割。理解正则表达式和`split()`方法的用法对于处理复杂的字符串处理任务至关重要。在实际编程中,根据需求选择合适的正则表达式和...
【标题】:“Horspool字符串匹配输入...通过这个实验,学生不仅可以掌握Horspool字符串匹配算法的原理和实现,还能学习到如何根据具体问题优化算法,提升其在实际应用中的性能,这对理解和应用计算机算法具有重要意义。
在Java编程语言中,分割字符串是一项常见的操作,它允许我们将一个长字符串分解成多个子字符串,每个子字符串对应原字符串中的某一部分。这通常通过使用`split()`方法来实现,该方法是`String`类的一个实例方法。让...
括号匹配是计算机科学中一个基础且关键的问题,主要用来检查一个字符串中的左右括号是否正确配对。例如,我们常见的括号有大括号`{}`、小括号`()`、中括号`[]`。 在这个描述中提到的程序,是利用栈来检查字符串中的...
模糊匹配是指在两个字符串之间进行比较时,允许一定程度的不精确性,如字符差异、位置差异等。常见的模糊匹配算法有Levenshtein距离、Jaccard相似度、余弦相似度、 Soundex编码等。 1. **Levenshtein距离**:...
在Java编程语言中,字符串处理是一项常见的任务,它涉及到对文本数据的各种操作,如编码转换、截取、加密和解密以及数值与字符串之间的转换。本组件提供了丰富的功能,简化了这些操作。以下是对该组件及其功能的详细...
在Java中,我们可以使用`java.util.regex`包中的`Pattern`和`Matcher`类来匹配和操作符合特定模式的字符串。对于提取括号内的内容,一个简单的正则表达式可以是`\((.*?)\)`,它匹配一对括号,并用`.*?`非贪婪地捕获...
在Java编程语言中,分解字符串是一项常见的任务,它涉及到对字符串进行分析,将字符串分割成多个子字符串。这个过程通常被称为字符串分割。在Java中,我们主要使用`String`类提供的`split()`方法来实现这一功能。...
本文将深入探讨在安卓2.2到5.1.1版本中如何进行字符串匹配与截取,并提供相关的函数说明。 首先,让我们从字符串匹配开始。在安卓中,最常用的字符串匹配方法是使用正则表达式。`java.util.regex`包提供了`Pattern`...
这是个比较难理解的算法,虽然代码就那么几行,但真正理解清楚还是要会时间的。
3.Build a program using Java array of string, you need to input 5 or more most famous universities in the world, and the annual tuition of each university. Please (1) Display the university name by ...
而"char_comp"文件可能包含了实现该字符串匹配功能的源代码。通常,这种函数会接收两个字符串作为输入参数,并通过某种方式转换它们(通常是转换为全大写或全小写),然后使用基本的字符串比较操作来确定它们是否...