牛客巅峰赛s2第八场C

青铜C 王者B B站讲解视频https://www.bilibili.com/video/BV1W5411G7cX?p=3

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef pair<int,int> PII;
#define so sizeof
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define lb lower_bound
#define ub upper_bound


const db esp=1e-5;
const int N=1e6+10,M=1e2+10,Max=1e5+5,inf=0x3f3f3f3f,mod=1e9+7;
const ll INF=0x3f3f3f3f3f3f3f3f;

int ne[N],n;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 给定一个字符串s，返回具有相同前缀后缀的子串的第二大长度，反之，返回-1即可。
     * @param s string字符串 代表题意中的字符串s
     * @return int整型
     */
    //求p[st,en)的ne[i]使得len(=1~ne)最长，在满足p[1~ne]与p[i-len~i]完全相同的情况下
    void getne(string &p,int st=1,int en=n){
        ne[st]=st-1;
        for(int i=st+1,j=st-1;i<en;i++){
            while(j!=st-1&&p[j+1]!=p[i]) j=ne[j];
            if(p[j+1]==p[i]) j++;
            ne[i]=j;
        }
    }
    int solve(string s) {
        // write code here
        s=" "+s;
        int n=s.size();
        getne(s,1,n);
        int ans=ne[n-1];

        if(ans==0) return -1;
        return ans;
    }
}T;