看毛片算法

给出两个字符串s1和s2，其中s2为s1的子串，求出s2在s1中所有出现的位置。\(n,m<=10^6\)。

众所周知，kmp算法是需要border数组的。\(border[i]\)表示前缀i的border的位置。

注意，字符串是从0开始编号的，算法中的所有数组也都是从零开始使用的。这样能使代码更易懂~

然后两张图就能够说明一切了：第一张表示求nxt，第二张表示匹配。

#include 
    
     #include 
     
      using namespace std;const int maxn=1e6+5;char s1[maxn], s2[maxn];int n1, n2, nxt[maxn];int main(){    scanf("%s", s1); scanf("%s", s2);    n1=strlen(s1); n2=strlen(s2);     int j=nxt[0]=-1;  //j:i-1的border位置     for (int i=1; i