原创内容，转载请注明原文网址：http://homeqin.cn/a/wenzhangboke/jishutiandi/youxikaifa/2018/1225/267.html
常州微信公众号开发-字符串匹配的三种方法
int strStr(string haystack, string needle) {
int i, hSize = haystack.size(), nSize = needle.size();
if(hSize < nSize)
return -1;
if(nSize == 0)
return 0;
for(i = 0; i <= hSize - nSize && haystack.substr(i, nSize) != needle; ++i);
return i <= hSize - nSize ? i : -1;
char hash(const string& str)
{
char all = 0;
for(auto c : str)
all ^= c;
return all;
}
//选定一个hash函数，对字符串hash，hash值不同一定是不同字符串
//由于hash值可能有冲突 所以hash值相同的字符并不一定相同 需要逐个字符再比较
//hash函数可以常州微信公众平台自己写，也可以用std::hash<string>
int strStr(string haystack, string needle) {
int i, hSize = haystack.size(), nSize = needle.size();
if(hSize < nSize)
return -1;
if(nSize == 0)
return 0;
//或者使用std::hash
//std::hash<string> hash;
char target = hash(needle);
for(i = 0; i <= hSize - nSize; ++i)
{
if(hash(haystack.substr(i,nSize)) == target && haystack.substr(i,nSize) == needle)
break;
}
return i <= hSize - nSize ? i : -1;
}
3.kmp
具体说明参考维基百科：https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
vector<int> buildNextArray(const string& s)
{
vector<int> next(s.size());
int i = 2, j = 0;
next[0] = -1;
if(s.size() > 1)
next[1] = 0;
while(i < s.size())
{
if(s[i-1] == s[j])
next[i++] = ++j;
else if(j > 0)
j = next[j];
else
next[i++] = 0;
}
return next;
}
int strStr(string haystack, string needle) {
int start = 0, i = 0, hSize = haystack.size(), nSize = needle.size();
if(hSize < nSize)
return -1;
if(nSize == 0)
return 0;
//kmp算法常州微信小程序开发
vector<int> next = buildNextArray(needle);
while(start <= hSize - nSize)
{
if(haystack[start + i] == needle[i])
{
if(++i == nSize)
return start;
}
else
{
start = start + i - next[i];
i = i > 0 ? next[i] : 0;
}
}
return -1;
}
上篇：上一篇：常州手机游戏开发-在二叉树中找路径
下篇：下一篇：常州微信小程序开发-各种字符串哈希函数比较
