iframe-proxy | Sunbelt Computer Software

102 lines (101 loc) · 1.97 KB

#include <string>
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
class Solution {
		int strStr(string s, string p) {
			return BF_strStr(s, p);
		/** TLE **/
		int slow_strStr(string s, string p) {
			if (p.empty()) {
				return 0;
			if (s.empty()) {
				return -1;
			char first = p[0];
			int n = s.size() - 1;
			int targetCount = p.size();
			for (int i = 0; i <= n; ++i) {
				if (s[i] != first) {
					while(++i <= n && s[i] != first);
				if (i <= n) {
					int j = i + 1;
					int end = j + targetCount - 1;
					for (int k = 1; j < end && s[j] == p[k];j++, k++);
					if (j == end)
						return i;
			return -1;
		int kmp_strStr(string s, string p) {
			if (p.empty())
				return 0;
			if (s.empty()) {
				return -1;
			int s_len = s.size(), p_len = p.size();
			int next[p_len], i = 0, j = -1;
			next[0] = -1;
			while (i < p_len - 1) {
				if (j == -1 || p[i] == p[j]) {
					i++, j++;
					if (p[i] != p[j])
						next[i] = j;
						next[i] = next[j];
				} else {
					j = next[j];
			i = 0, j = 0;
			while (i < s_len && j < p_len) {
				if (j == -1 || s[i] == p[j])
					i++, j++;
					j = next[j];
			if (j == p_len)
				return i - j;
			return -1;
		/* 暴力枚举算法
		 *  BF(Brute Force)普通的模式匹配算法
		int BF_strStr(string s, string p) {
			int s_len = s.size();
			int p_len = p.size();
			for (int i = 0; ; ++i) {
				for (int j = 0; ; j++) {
					if (j == p.size())
						return i;
					if (i + j == s.size())
						return -1;
					if (s[i + j] != p[j])
						break;
			return -1;
		int BM_strStr(string s, string p) {
int main(int argc, char **argv)
	Solution solution;
	string s, p;
	cout << solution.strStr(s, p) << endl;
	s = "abcd";
	cout << solution.strStr(s, p) << endl;
	s = string(), p = "abcd";
	cout << solution.strStr(s, p) << endl;
	while (cin >> s >> p) {
		cout << solution.strStr(s, p) << endl;

Sunbelt Computer Software

PL/B Language Development and Support

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Sunbelt Computer Software

PL/B Language Development and Support

Uh oh!

FilesExpand file tree

strstr.cpp

Latest commit

History

strstr.cpp

File metadata and controls