String match KMP BF

string matching ?

Simply put : Given two strings S, T stay Main string S Find Pattern T

BF

C++ Code

/** * @brief brutal force  violence  * * @param str  character string  * @param pat  Pattern  * @return int  Initial subscript or -1 I didn't find  */
int bf(string str, string pat) {
    
	for (size_t i = 0; i < str.length(); i++) {
    
		size_t j = 0, k = i;
		for (; j < pat.size();) {
    
			if (str[k] == pat[j])
				++k, ++j;
			else
				break;
		}
		if (j == pat.size())
			return i;
	}
	return -1;
}

Java Code

    public static int indexOf(byte[] value, int valueCount, byte[] str, int strCount, int fromIndex) {
    
        byte first = str[0];
        int max = (valueCount - strCount);
        for (int i = fromIndex; i <= max; i++) {
    
            // Look for first character.
            if (value[i] != first) {
    
                while (++i <= max && value[i] != first);
            }
            // Found first character, now look at the rest of value
            if (i <= max) {
    
                int j = i + 1;
                int end = j + strCount - 1;
                for (int k = 1; j < end && value[j] == str[k]; j++, k++);
                if (j == end) {
    
                    // Found whole string.
                    return i;
                }
            }
        }
        return -1;
    }

KMP

The core idea is that the main string does not go back
use next After the array records the current position mismatch , The pattern string should start there again
The difficulty is how to find next Array , Here are two ways

C++ Code

/** * @brief kmp  Use next Array  * * @param str  character string  * @param pat  Pattern  * @return int */
int kmp(string str, string pat) {
    
	const int N = pat.length();
	int next[N];
	//  Initial Hu next
	next[0] = -1;
	for (int k = 0, j = 1; j < N; ++j) {
    
		next[j] = k;
		while (k > 0 && pat[j] != pat[k])
			k = next[k];
		if (pat[j] == pat[k])
			++k;
	}
	//  matching 
	int i = 0, j = 0;
	for (; i < str.length();) {
    
		if (j == -1 || str[i] == pat[j])
			++j, ++i; //  success ++
		else
			j = next[j]; //  Failure backtracking 
		if (j == pat.length())
			return i - j; //  Initial subscript 
	}
	return -1;
}
/** * @brief Get the "next" array * * @param next  Array  * @param t  Pattern  */
void get_next(int next[], string t) {
    
	next[0] = -1;
	for (int j = 0, k = -1; j < t.length() - 1;) {
    
		if (k == -1 || t[j] == t[k]) {
    
			j++;
			k++;
			next[j] = k;
		} else
			k = next[k];
	}
}

Test code

int main(int argc, char const* argv[]) {
    
	int a = bf("sdsdfaaregwr", "sdf");
	cout << a << '\n';
	a = bf("gsfwesgfvsfghj", "sdf");
	cout << a << '\n';
	string str = "abcbababcabcdf";
	string pat = "bababcabc";
	int idx = kmp(str, pat);
	cout << idx;
	return 0;
}