本文共 543 字，大约阅读时间需要 1 分钟。

链接：

题目大意：

给两个字符串s1和s2, 求出是s1的前缀并且是s2的后缀的最长的字符串。

分析与总结：

真正理解好KMP算法，这题就是水题。

首先求出s1的失配函数，然后在s2中寻找s1字符串。 

在寻找字符串过程中，会有一个状态值j，这个值表示的是当前在s2中已经匹配了多少个s1的字符。 所以，全部匹配完后，最后j的值就是以s2的最后一个字符结尾，和s1的前缀相匹配的最长字符串。也就是所求的答案了。

还有一种方法：

网上有不少题解貌似都是把s1和s2拼接起来成s3，然后求s3自身的next，原理其实是一样的。

代码：

#include
   
    #include
    
     #include
     
      using namespace std;const int MAXN = 50005;char s1[MAXN];char s2[MAXN];int  f[MAXN];void getFail(char *p, int *f){    int n=strlen(p);    f[0]=f[1]=0;    for(int i=1; i
     
    
   

          原创  ， By   D_Double  (转载请标明)