class KMP
{
public:
void getNext(int* next, const string str)
{
int j = -1;
next[0] = j;
for (int i = 1; i < str.size(); i++)// 注意i从1开始
{
while (j >= 0 && str[i] != str[j+1])// 前后缀不相同了
{
j = next[j];// 向前回溯
}
if (str[i] == str[j+1]) // 找到相同的前后缀
{
j++;
}
next[i] = j;// 将j（前缀的长度）赋给next[i]
}
}
int sameStr(string str1, string str2)
{
if (str2.size() == 0)
return 0;
int* next = new int[str2.size()];
int j = -1;//因为next数组里记录的起始位置为 - 1
getNext(next, str2);
for (int i = 0; i < str1.size(); i++)
{
while (j >= 0 && str1[i] != str2[j+1])
{
j = next[j];
}
if (str1[i] == str2[j+1])
{
j++;
}
if (j == str2.size() - 1)
{
return i - str2.size() + 1;
}
}
return -1;
}
};
