给出字符串a和字符串b，保证b是a的一个子串，请你输出b在a中第一次出现的位置。
仅一行包含两个字符串a和b
仅一行一个整数
abcd bc
2
字符串的长度均不超过100
Pascal用户请注意：两个字符串之间可能包含多个空格
注意：依旧是模板，但是这次是自己打的，发现了一些问题，WA了两次因为输出SB了233
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 5 using namespace std; 6 7 char a[110],b[110]; 8 int lena,lenb,sp[110]; 9 10 void calcsp() 11 { 12 int t; 13 sp[0]=-1; 14 for (int i=0;i<lena;i++) 15 { 16 t=sp[i]; 17 while (t!=-1 && a[t]!=a[i]) t=sp[t]; //注意是&& 18 sp[i+1]=++t; 19 } 20 } 21 22 void kmp() 23 { 24 int t=0,k=0; 25 calcsp(); 26 while (t<lena && k<lenb) 27 { 28 if (k==-1 || a[t]==b[k]) t++,k++; //注意从头匹配k==-1 29 else k=sp[k]; 30 if (k==lenb) cout<<t-lenb+1<<endl,t=0x7f; 31 } 32 } 33 34 int main() 35 { 36 cin>>a>>b; 37 lena=strlen(a); 38 lenb=strlen(b); 39 kmp(); 40 return 0; 41 }
原文：http://www.cnblogs.com/DMoon/p/5198741.html
