1 条题解

  • 0
    @ 2024-3-6 19:01:50
    #include <bits/stdc++.h>
    using namespace std;
    const int maxn = 1.1e7 + 5;
    char s[maxn], a[maxn*2+1];
    int n, p[maxn*2+1], mid, mr, ans;
    
    int main() {
    	scanf("%s", s);
    	a[n++] = '$';
    	a[n++] = '#';
    	for (int i = 0; s[i]; i++)
    		a[n++] = s[i], a[n++] = '#';
    	a[n++] = '^';
    	for (int i = 0; i < n; i++) {
    		if (i < mr) 
    			p[i] = min(p[2 * mid - i], mr - i);
    		else 
    			p[i] = 1;
    		while (a[i-p[i]] == a[i+p[i]]) 
    			p[i]++;
    		if (i + p[i] > mr) {
    			mr = i + p[i];
    			mid = i;
    		}
    		ans = max(ans, p[i] - 1);
    	}
    	printf("%d\n", ans);
    	return 0;
    }
    
    • 1

    信息

    ID
    78
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    4
    已通过
    1
    上传者