本文已参与「新人创造礼」活动,一起开启掘金创造之路。

原题:重复叠加字符串匹配

从 重复叠加字符串匹配 看 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来检测,其实能够优化一下:

  1. 先计算前面b.size()个字符的hash值;

  2. 比较是否等于方针hash值

  3. 假如不等于,(当时hash值-(当时窗口首字符-'a')*26^k)*26 + 窗口右移新加进来的字符-'a'

  4. 这样只用完好的遍历一遍 字符串a 就能够知道它 有没有包含 子串b,杂乱度为 O(n);可是涉及到之前的取余操作,又要额外考虑下,当时窗口的hash值是不是取过余;

  5. 而假如每次都一个个字符比,那么杂乱度达到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 办法 原理仍是用的逐一字符比较,没有用其他作用略微高但很杂乱的办法;