#include <string>
#include <vector>
using namespace std;
vector<int> * kmp_next(string &substr)
...{
//next[i]存储的数字意义:
//当text[tp]与substr[i+1]不匹配的时候,
//应该让text[tp]来继续与substr[next[i]]来进行比较,
//因为substr[0]...substr[next[i]-1]与text[next[i]-tp]...text[tp-1]相同,
static vector<int> next(substr.length());
next[0]=0;
int temp;
for (int i=1;i<substr.length();i++)
...{
temp = next[i-1];//Get last value
while(substr[i]!=substr[temp] && temp>0)
temp=next[temp-1];
if (substr[i]==substr[temp])
next[i]=temp+1;//前面存在字符和当前比较的字符的前一个字符相同的,所以找那个字符的下
//当text[tp]与substr[i+1]不匹配的时候,
//应该让text[tp]来继续与substr[next[i]]来进行比较,
//因为substr[0]...substr[next[i]-1]与text[next[i]-tp]...text[tp-1]相同,
static vector<int> next(substr.length());
next[0]=0;
int temp;
for (int i=1;i<substr.length();i++)
...{
temp = next[i-1];//Get last value
while(substr[i]!=substr[temp] && temp>0)
temp=next[temp-1];
if (substr[i]==substr[temp])
next[i]=temp+1;//前面存在字符和当前比较的字符的前一个字符相同的,所以找那个字符的下
//一 个 字符来比较
else
next[i]=0;//前面没有字符和当前比较的字符的前一个字符相同的的,所以找来substr的首字符来重新比较
}
return &next;
}
bool kmp_search(string& text,string &substr,int&pos)
...{
vector<int> *next = kmp_next(substr);
int j=0;
int i=0;
for (i=0;i<text.length();i++)
...{
while(text[i]!=substr[j]&&j>0)
j=(*next)[j-1];
if (text[i]==substr[j])
j++;
if (j==substr.length())
...{
pos = i-j+1;
return true;
}
}
if (i==text.length())
...{
return false;
}
}
int search(string&text, string &substr)
...{
int subpos =0;
int count=0;
string tmptext = text;
while (kmp_search(tmptext,substr,subpos))
...{
count++;
tmptext = tmptext.substr(subpos+substr.length(),text.length()-(subpos+substr.length()));
}
return count;
}
else
next[i]=0;//前面没有字符和当前比较的字符的前一个字符相同的的,所以找来substr的首字符来重新比较
}
return &next;
}
bool kmp_search(string& text,string &substr,int&pos)
...{
vector<int> *next = kmp_next(substr);
int j=0;
int i=0;
for (i=0;i<text.length();i++)
...{
while(text[i]!=substr[j]&&j>0)
j=(*next)[j-1];
if (text[i]==substr[j])
j++;
if (j==substr.length())
...{
pos = i-j+1;
return true;
}
}
if (i==text.length())
...{
return false;
}
}
int search(string&text, string &substr)
...{
int subpos =0;
int count=0;
string tmptext = text;
while (kmp_search(tmptext,substr,subpos))
...{
count++;
tmptext = tmptext.substr(subpos+substr.length(),text.length()-(subpos+substr.length()));
}
return count;
}