include

include

include

include

include

include

include

include

include

include

using namespace std;

void GetNext(int next[], String t) { int i = 0, j = -1; next[0] = -1; while (i < t.length() - 1) { if (j == -1 || t[i] == t[j]) { i++; j++;
} else { j = next[j]; } } }

int KMP(String s, String t) { int next[100], i = 0, j = 0; GetNext(next, t); while (i < s.length() && j < t.length()) { if (j == -1 || s[i] == t[j]) { i++; j++; } else { j = next[j]; } } if (j >= t.length()) { return (i - t.length());//匹配成功，返回起始位置 } else { return -1; } }