1 条题解

  • 0
    @ 2023-10-31 21:01:06
    #include <bits/stdc++.h>
    using namespace std;
    const int maxn = 1e6 + 5;
    int n, nxt[maxn];
    char s[maxn];
    
    void cal_nxt() { 
    	nxt[1] = 0;
    	for (int i = 2, j = 0; i <= n; i++) {
    		while (j && s[j+1] != s[i])
    			j = nxt[j];
    		if (s[j+1] == s[i]) j++;
    		nxt[i] = j;
    	}
    }
    int main() {
    	scanf("%d", &n);
    	scanf("%s", s+n+1);	// s[n+1..n+n]
    	strncpy(s+1, s+n+1, n); // s[1..n]
    	reverse(s+1, s+n+1);
    	n *= 2;
    	cal_nxt();
    	int p = n;
    	while (p > n/2)
    		p = nxt[p];
    	printf("%d\n", n/2 - p);
    	return 0;
    }
    
    
    • 1

    信息

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