关于manacher的一点疑问
查看原帖
关于manacher的一点疑问
237530
rzh123楼主2023/7/24 06:50

经过测试这个代码能过:

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
constexpr int N=3e7+7;
char s[N];
int n,pl[N],ans;
int main(){
    s[0]='&';s[++n]='|';
    while((s[++n]=getchar())!=EOF&&!isspace(s[n])) s[++n]='|';
    --n;
    int mid{0},r{0};        // 之前找到的延伸最右的回文串的中点、右边界
    for(int i{1};i<=n;++i){
        if(i<=r) pl[i]=min(pl[2*mid-i],r-i+1);
        else pl[i]=1; 
        while(s[i-pl[i]]==s[i+pl[i]]) ++pl[i];
        // if(i+pl[i]-1>=r)
            mid=i,r=i+pl[i]-1;
        ans=max(ans,pl[i]-1); 
    } printf("%d\n",ans);
    return 0;
}

为什么常见的写法都要加上 if(i+pl[i]-1>=r)?

2023/7/24 06:50
加载中...