/*若主串长度为N，子串长度为M，暴力求解时间复杂度为O(M x N)。 KMP 算法时间复杂度O(M)+O(N)。算法最主要的就是子串的next数组的构造了。 首先生成子串的next_arr数组，这个数组长度与子串长度一致。数组中第i个 元素next_arr[i]的含义是B[i]之前的字符串B[0...i-1]中，必须以B[i-1]结尾 的后缀子串（不能包含B[0]）与必须以B[0]开头的前缀子串（不能包含B[i-1]） 最大匹配长度是多少，这个长度就是next_arr[i]的值。子串用处：当到第i个 元素与主串不匹配的时候，可以不一定要从子串头和主串初始匹配时的下一个 元素做起点开始匹配。因为next_arr数组记录了子串第i个元素之前的子串特性。 若子串在B[i]处于主串A[j]处不匹配，则j位置不变，下次从B[next_arr[i]]处 继续和A[j]相比。*/ #include<iostream> #include<string> using namespace std; //求子串next数组 int* getnext_arr(string B) { int len = B.length(); int* next = new int[len]; next[0] = -1; if(len==1)   return next;   next[1] = 0;   int pos = 2;   int cn = 0;   while(pos < len)   {   if(B[pos-1] == B[cn]) next[pos++] = ++cn; else if(cn > 0) cn = next[cn]; else next[pos++] = 0; } return next; } //匹配，若能匹配，返回主串匹配起始的下标，若不能则返回-1 int getIndex(string A, string B) { if(A == "" || B == "" || B.length() < 1 || A.length() < B.length()) return -1; int Ai = 0, Bi=0; int *next = new int[B.length()]; next = getnext_arr(B); while(Ai < A.length() && Bi < B.length()) { if(A[Ai] == B[Bi]) { Ai++; Bi++; } else if(next[Bi] == -1) { Ai++; } else { Bi = next[Bi]; } } return Bi == B.length() ? Ai - Bi : -1; } int main() { string A,B; while(cin>> A >> B) { cout<<getIndex(A,B) <<endl; } return 0; }