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)