Java String源码contains题解重复叠加字符串匹配

目录
  • 原题
  • 解题思路
    • Java String contains 函数

原题

重复叠加字符串匹配

解题思路

解题思路已经写在代码中了；

class Solution {
public:
	bool contain(string &a, string &b, long long hash_b)
	{
		for (int i = 0; i <= a.size() - b.size(); i++)
		{
			int k = 0;
			long long hash_a = 0;
			while (k < b.size())
			{
				hash_a = (hash_a * 26 + a[i + k] - 'a') % INT32_MAX;
				k++;
			}
			if (hash_b == hash_a)
				return true;
		}
		return false;
	}
	int repeatedStringMatch(string a, string b)
	{
		// 1、统计a每个字符出现次数、b每个字符出现次数，如果b有某字符而a没有，返回-1
		vector<int> rec_a(30, 0);
		vector<int> rec_b(30, 0);
		for (char c : a)
		{
			rec_a[c - 'a']++;
		}
		long long hash_b = 0;
		int i = 0;
		for (char c : b)
		{
			hash_b = (hash_b * 26 + c - 'a') % INT32_MAX;
			rec_b[c - 'a']++;
		}
		for (int i = 0; i < 30; i++)
		{
			if (rec_b[i] > 0 && rec_a[i] == 0)
			{
				return -1;
			}
		}
		// 2.1 本身b就是a的字串，用hash
		if (a.size() >= b.size() && contain(a, b, hash_b))
		{
			return 1;
		}
		// 2.2 最大重叠不超过Bsize/Asize + 2
		string aa = a;
		for (int i = 2; i <= b.size() / a.size() + 2; i++)
		{
			aa += a;
			if (aa.size() < b.size())
				continue;
			if (contain(aa, b, hash_b))
			{
				return i;
			}
		}
		return -1;
	}
};

但是C++毕竟没有类似Java的contains函数，所以检查a字符串是否包含b就没有那么方便，我这里自己实现的是利用hash来检测，其实可以优化一下：

  • 先计算前面b.size()个字符的hash值；
  • 比较是否等于目标hash值
  • 如果不等于，(当前hash值-(当前窗口首字符-'a')*26^k)*26 + 窗口右移新加进来的字符-'a'；
  • 这样只用完整的遍历一遍 字符串a 就能够知道它 有没有包含 子串b，复杂度为 O(n)；但是涉及到之前的取余操作，又要额外考虑下，当前窗口的hash值是不是取过余；
  • 而如果每次都一个个字符比，那么复杂度达到O(nm)；

Java String contains 函数

于是对 Java String 里面的 contains 函数很好奇，它内部怎么实现的，就翻了下源码，如下：

// String.contails(String s)：
// 返回this字符串是否包含 子串s
public boolean contains(CharSequence s) {
    return this.indexOf(s.toString()) >= 0;
}

// String.indexOf(String s)
// 返回this字符串中子串s的首字符索引
........
// 中间的几个函数就省略了，都是一些特殊情况（比如this字符串的长度小于s字符串的长度，直接返回-1这种），
// 最后实现是在这个函数里
public static int indexOfLatin1Unsafe(byte[] src, int srcCount, byte[] tgt, int tgtCount, int fromIndex) {
    assert fromIndex >= 0;
    assert tgtCount > 0;
    assert tgtCount <= tgt.length;
    assert srcCount >= tgtCount;
    // 目标字符串的第一个字符
    char first = (char)(tgt[0] & 255);
    // 最多找max次
    int max = srcCount - tgtCount;
	// 从fromIndex处开始找
    for(int i = fromIndex; i <= max; ++i) {
    	// 如果该字符不等于first，接着i++，直到找到与first字符相等
        if (getChar(src, i) != first) {
            do {
                ++i;
            } while(i <= max && getChar(src, i) != first);
        }
        if (i <= max) {
            int j = i + 1;
            int end = j + tgtCount - 1;
			// 一个个字符逐个比较
            for(int k = 1; j < end && getChar(src, j) == (tgt[k] & 255); ++k) {
                ++j;
            }
			// 如果j==end 说明全部遍历完都符合条件，返回首字符位置i
            if (j == end) {
                return i;
            }
        }
    }
    return -1;
}

可以看出 Java String 的 contains 方法 原理还是用的逐个字符比较，没有用别的效果稍微高但很复杂的方法；

以上就是Java String源码contains题解重复叠加字符串匹配的详细内容，更多关于Java String源码contains的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • java中String字符串删除空格的七种方式

    java中String字符串删除空格的七种方式

    目录 trim() strip() stripLeading() 和 stripTrailing() replace replaceAll replaceFirst 总结 在Java中从字符串中删除空格有很多不同的方法,如trim,replaceAll等.但是,在JDK 11添加了一些新的功能,如strip.stripLeading.stripTrailing等. 想要从String中移除空格部分,有多少种方法,下面介绍JDK原生自带的方法,不包含第三方工具类库中的类似方法 trim() : 删

  • Java String中的split方法使用总结

    目录 String中split方法使用 1.一般用法 2.需要转义的分隔符 3.多个符号作为分隔符 4.空值的存储 String.split()需要的转义字符 转义字符 String中split方法使用 String的split()方法用于按传入的字符或字符串对String进行拆分,返回拆分之后的数组. 1.一般用法 用一般的字符,例如@或,等符号做分隔符时: String address="上海@上海市@闵行区@吴中路"; String[] splitAddr=address.spl

  • Java实现字符串的分割(基于String.split()方法)

    Java实现字符串的分割(基于String.split()方法)

    目录 前言 一.JDK-1.8-API文档说明(推荐阅读) 二.简单的使用 1.单个字符分隔 2.正则表达式 三.Java源码分析 1.源代码的测试代码 2.源代码运行原理图示 3.解读完代码后的总结(推荐阅读) 四.limit参数使用区别 1.limit=0 2.limit<0 3.limit>0 五.易错点(推荐阅读) 1.分割到第一个字符 2.转义字符\ 3.正则表达式修饰符不可用 总结 前言 本章对Java如何实现字符串的分割,是基于jDK1.8版本中的String.split()方法

  • Java如何将字符串String转换为整型Int

    Java如何将字符串String转换为整型Int

    目录 用法 注意点 性能比较 用法 在java中经常会遇到需要对数据进行类型转换的场景,String类型的数据转为Int类型属于比较常见的场景,主要有两种转换方法: 1. 使用Integer.parseInt(String)方法 2. 使用Integer.valueOf(String)方法 具体demo如下: public void convert() { // 1.使用Integer.parseInt(String) String str1 = "31"; Integer num1

  • Java String之contains方法的使用详解

    目录 Java String contains方法 小结一下 String的contain()函数用法 例如 Java String contains方法 package api.api; public class App1 {undefined public static void main(String[] args) {undefined String num = "WKCON190400111"; if (num.contains("CON")) {unde

  • java开发使用StringUtils.split避坑详解

    java开发使用StringUtils.split避坑详解

    目录 正文 StringUtils.split 的坑 StringUtils.split 源码分析 如何解决? 正文 在日常的 Java 开发中,由于 JDK 未能提供足够的常用的操作类库,通常我们会引入 Apache Commons Lang 工具库或者 Google Guava 工具库简化开发过程.两个类库都为 java.lang API 提供了很多实用工具,比如经常使用的字符串操作,基本数值操作.时间操作.对象反射以及并发操作等. <dependency> <groupId>

  • Java中实现String字符串用逗号隔开

    Java中实现String字符串用逗号隔开

    目录 String字符串用逗号隔开 1.如果我们的需求是要让分隔符号可以兼容中英文逗号 2.如果我们的需求是取到第一个逗号前面的字符串 以逗号为分割符拼接字符串的技巧 实现代码如下所示 String字符串用逗号隔开 在Java中,有两个方法可以用逗号把String分开 一个是 public String[] split(String regex) { return split(regex, 0); } 另一个是 public String[] split(String regex, int li

  • Java String源码contains题解重复叠加字符串匹配

    Java String源码contains题解重复叠加字符串匹配

    目录 原题 解题思路 Java String contains 函数 原题 重复叠加字符串匹配 解题思路 解题思路已经写在代码中了: class Solution { public: bool contain(string &a, string &b, long long hash_b) { for (int i = 0; i <= a.size() - b.size(); i++) { int k = 0; long long hash_a = 0; while (k < b

  • Java String源码分析并介绍Sting 为什么不可变

    Java String源码分析并介绍Sting 为什么不可变

    Java String源码分析 什么是不可变对象? 众所周知, 在Java中, String类是不可变的.那么到底什么是不可变的对象呢? 可以这样认为:如果一个对象,在它创建完成之后,不能再改变它的状态,那么这个对象就是不可变的.不能改变状态的意思是,不能改变对象内的成员变量,包括基本数据类型的值不能改变,引用类型的变量不能指向其他的对象,引用类型指向的对象的状态也不能改变. 区分对象和对象的引用 对于Java初学者, 对于String是不可变对象总是存有疑惑.看下面代码: String s =

  • java String源码和String常量池的全面解析

    1. String 介绍,常用方法源码分析 2. String 常量池分析 常用方法 equals trim replace concat split startsWith 和 endsWith substring toUpperCase() 和 toLowerCase() compareTo String 介绍 String类被final所修饰,也就是说String对象是不可变量,并发程序最喜欢不可变量了.String类实现了Serializable, Comparable, CharSequ

  • java集合类源码分析之Set详解

    Set集合与List一样,都是继承自Collection接口,常用的实现类有HashSet和TreeSet.值得注意的是,HashSet是通过HashMap来实现的而TreeSet是通过TreeMap来实现的,所以HashSet和TreeSet都没有自己的数据结构,具体可以归纳如下: •Set集合中的元素不能重复,即元素唯一 •HashSet按元素的哈希值存储,所以是无序的,并且最多允许一个null对象 •TreeSet按元素的大小存储,所以是有序的,并且不允许null对象 •Set集合没有ge

  • Java集合源码全面分析

    Java集合源码全面分析

    Java集合工具包位于Java.util包下,包含了很多常用的数据结构,如数组.链表.栈.队列.集合.哈希表等.学习Java集合框架下大致可以分为如下五个部分:List列表.Set集合.Map映射.迭代器(Iterator.Enumeration).工具类(Arrays.Collections). 从上图中可以看出,集合类主要分为两大类:Collection和Map. Collection是List.Set等集合高度抽象出来的接口,它包含了这些集合的基本操作,它主要又分为两大部分:List和Se

  • 以武侠形式理解Java LinkedList源码

    以武侠形式理解Java LinkedList源码

    目录 一.LinkedList 的剖白 二.LinkedList 的内功心法 三.LinkedList 的招式 1)招式一:增 2)招式二:删 3)招式三:改 4)招式四:查 四.LinkedList 的挑战 一.LinkedList 的剖白 大家好,我是 LinkedList,和 ArrayList 是同门师兄弟,但我俩练的内功却完全不同.师兄练的是动态数组,我练的是链表. 问大家一个问题,知道我为什么要练链表这门内功吗? 举个例子来讲吧,假如你们手头要管理一推票据,可能有一张,也可能有一亿张

  • Java HashMap源码深入分析讲解

    1.HashMap是数组+链表(红黑树)的数据结构. 数组用来存放HashMap的Key,链表.红黑树用来存放HashMap的value. 2.HashMap大小的确定: 1) HashMap的初始大小是16,在下面的源码分析中会看到. 2)如果创建时给定大小,HashMap会通过计算得到1.2.4.8.16.32.64....这样的二进制位作为HashMap数组的大小. //如何做到的呢?通过右移和或运算,最终n = xxx11111.n+1 = xx100000,2的n次方,即为数组大小 s

  • java TreeMap源码解析详解

    java TreeMap源码解析详解

    java TreeMap源码解析详解 在介绍TreeMap之前,我们来了解一种数据结构:排序二叉树.相信学过数据结构的同学知道,这种结构的数据存储形式在查找的时候效率非常高. 如图所示,这种数据结构是以二叉树为基础的,所有的左孩子的value值都是小于根结点的value值的,所有右孩子的value值都是大于根结点的.这样做的好处在于:如果需要按照键值查找数据元素,只要比较当前结点的value值即可(小于当前结点value值的,往左走,否则往右走),这种方式,每次可以减少一半的操作,所以效率比较高

  • Java从源码看异步任务计算FutureTask

    Java从源码看异步任务计算FutureTask

    目录 了解一下什么是FutureTask? FutureTask 是如何实现的呢? FutureTask 运行流程 FutureTask 的使用 前言: 大家是否熟悉FutureTask呢?或者说你有没有异步计算的需求呢?FutureTask就能够很好的帮助你实现异步计算,并且可以实现同步获取异步任务的计算结果.下面我们就一起从源码分析一下FutureTask. 了解一下什么是FutureTask? FutureTask 是一个可取消的异步计算. FutureTask提供了对Future的基本实

  • Java CopyOnWriteArrayList源码超详细分析

    Java CopyOnWriteArrayList源码超详细分析

    目录 一.概述 二.类图 三.核心方法 1.add() 2.set() 3.remove() 4.get() 5.size() 四.总结 一.概述 CopyOnWriteArrayList是基于写时复制技术实现的,适用于读多写少场景下的线程安全的并发容器.读操作永远不会加锁,读读.读写都不会冲突,只有写写需要等待.写操作时,为了不影响其它线程的读取,它会进行一次自我复制,待数据写入完成后再替换array数组.array数组是被volatile修饰的,它被修改后可以被其他线程立刻发现. publi

随机推荐