class Solution {
public:
int strStr(string haystack, string needle) {
int hay_len = haystack.length();
int needle_len = needle.length();
int i = 0, j = 0;
int* next = new int[needle_len];
getNext(needle, next);
while(i < hay_len && j < needle_len){
if(j == -1 || haystack[i] == needle[j]){
++i;
++j;
}
else{
j = next[j];
}
}
if(j >= needle_len)
return i - j;
else
return -1;
}
public:
void getNext(string needle, int next[]){
int n = needle.length();
int j = -1;
int i = 0
next[0] = -1;
while(i < n) {
if (j == -1 || needle[i] == needle[j]) {
++i;
++j;
next[i] = j;
}
else
j = next[j];
}
}
};
# include <iostream>
# include <cstring>
# include <algorithm>
using namespace std;
int next_[100];
void get_next(char *T)
{
int i = 1;
int j = 0;
next_[1] = 0;
int len = strlen(T);
while (i < len)
{
if (j == 0 || T[i] == T[j])
{
++i;
++j;
next_[i] = j;
}
else
{
j = next_[j];
}
}
for (i = 0; i < len; i++)
{
cout << next_[i] << " ";
}
cout << endl;
}
bool KMP(char *S, char *T)
{
cout << "begin" << endl;
int i = 1;
int j = 1;
int len_s = strlen(S);
int len_t = strlen(T);
while (i < len_s && j < len_t)
{
if (j == 0 || S[i] == T[j])
{
++i;
++j;
}
else
{
j = next_[j];
}
}
cout << j << endl;
if (j >= len_t)
{
cout << "hello" << endl;
return true;
}
else
return false;
}
int main()
{
char S[100] = "0aaaaaaabcdefa";
char T[100] = "0aaaabcd";
next_[0] = 1;
memset(next_, 0, sizeof(next_));
get_next(T);
bool k = KMP(S, T);
cout << k << endl;
}