http://tjuacm.chaosheng.top/problem.php?id=1259
https://vjudge.net/problem/HDU-2594
字符串匹配KMP，太不熟练了，这个算法一直一知半解。
参考：
https://blog.csdn.net/weixin_44606952/article/details/97654887?utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromMachineLearnPai2%7Edefault-1.baidujs&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromMachineLearnPai2%7Edefault-1.baidujs

先发一个暴力，WA有没有处理好的情况
如
llljs
mkllll
会输出0，但是实际应该是3。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 50010;

int main(){
    string s1, s2;
    while(cin >> s1 >> s2){
        //cin >> s2;
        int n = s1.size(); 
        int m = s2.size();
        if(n == 0 || m == 0){
            printf("0\n");
            continue;
        }
        int i = 0, j = 0;
        int len = 0;
        while(i < n && j < m){
            if(s1[i] == s2[j]){
                i++;
                j++;
                len++;
            }else{
                i = 0;
                j++;
                len = 0;
            }
            //printf("i = %d j = %d len = %d \n", i, j, len);
        } 

        if(j == m && len != 0){
            printf("%s %d\n", s1.substr(0, len).c_str(), len);
        }else{
            printf("0\n");
        }
    }
    return 0;
}

AC代码，用到KMP

KMP的next数组讲解 https://www.bilibili.com/video/BV1jb411V78H?from=search&seid=4819368457483381295
实现 https://blog.csdn.net/loterior/article/details/79104602

这个题是KMP的应用。本质上就是找前一个字符串的前缀和后一个字符串的后缀相同的串，使用 KMP 进行匹配时，注意当模式串 s1 到达结尾时，需要更新指针位置，返回值也需要返回前缀位置
kmp就是一个不断匹配的过程，但是当第一个字符串（就是要求next数组的）长度小于第二个字符串时，会出现匹配突然断了的情况，这个时候的，就要j=next[j]，重新找到最近的点继续匹配，一直匹配到最后，既然要匹配到最后，那么肯定能够知道前缀和后缀的最大匹配，也就是最后的j值。

参考 https://blog.csdn.net/u011815404/article/details/87983299

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 50010;

int nextt[N];

void getNext(string s){
    int n = s.size();
    int i = 0, j = -1;
    nextt[i] = j;
    while(i < n){
        if(j == -1 || s[i] == s[j]){
            i++;
            j++;
            nextt[i] = j;
        }else{
            j = nextt[j];
        }
    }
} 

int kmp(string s2, string s1){
    getNext(s1);
    int n = s1.size(); 
    int m = s2.size();
    int i = 0, j = 0;
    while(i < m && j < n){
        if(j == -1 || s2[i] == s1[j]){
            i++;
            j++;
            if(j == n && i != m){//当模式串到达结尾时，回到指定位置
                j = nextt[j];
            }
        }else{
            j = nextt[j];
        }
    }

    return j; //返回前缀的位置 
}

int main(){
    string s1, s2;
    while(cin >> s1 ){
        cin >> s2;
        int n = s1.size(); 
        int m = s2.size();
        if(n == 0 || m == 0){
            printf("0\n");
            continue;
        }

        int res = kmp(s2, s1);  
        if(res != 0){
            printf("%s %d\n", s1.substr(0, res).c_str(), res);
        }else{
            printf("0\n");
        }
    }
    return 0;
}