假设我们有一个一定个数的字母组成字串,我给每个字母分配一个素数,从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实现字符串的匹配.doc
主要介绍了Java中使用正则表达式实现字符串匹配,字符串查找,匹配,替换,正则无不能做,特别是灵活的运用子串匹配,感兴趣的小伙伴们可以参考一下
2019年Java实现字符串的匹配.pdf
用Boyer-Moore实现字符串匹配问题。算法中有坏字符移动表和好后缀移动表的创建方法。代码有注视供参考。
主要介绍了java实现求两个字符串最大公共子串的方法,详细的描述了两个字符串的最大公共子串算法的实现,需要的朋友可以参考下
这是个比较难理解的算法,虽然代码就那么几行,但真正理解清楚还是要会时间的。
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 ...
自己做的,能用栈实现括号匹配,程序很简单实用
使用java实现对两个字符串进行比较分析其相似度。
java 数组和字符串
java 字符串 删除空格 匹配删除字符
使用递归实现,字符串模糊匹配,看设置允许匹配错误数。
Java 字符串与文本相关实例源码,比如不可变字符串与限定字符串、字符串的比较、提取子串、修改缓冲区中的字符串、判断回文串、正则表达式、字符串匹配、正则表达式语法等,还一一些比如用于比较两个变量是否引用同...
JAVA两个字符串比较匹配字数
java实现关于字符串的符号匹配帮助类
此资源属于算法分析课程的实验,只供学习使用。本人很少上CSDN,有兴趣,有需要的话可以发E-MAIL:hzz865@21cn.com
java去掉字符串中匹配的字符串
两字符串比较返回重复个数,java的,课后一作业,随便写写
java 利用正则表达式从字符串中提取省、市、区、镇、乡等区域名称(包含少数民族地区),支持地址中无省,无市,无县情况。