Description This semester, various UFPE competitors had classes of a discipline called Theoretical Informatics. One of the major studied concepts was Turing Machines ™.
A TM is basically a system that has a tape with infinite memory cells to the right and a head pointer that is always pointing to one cell at a given moment.
A known fact in computer science is that every algorithm has an equivalent TM.
There are many TM variations and some of them has capability differences. One of these variations are the Deciders, which are machines that always stops (never entering infinite loop state), “accepting” or “rejecting” any given input.
One of the recommended exercises of the discipline was the following: “Describe a Decider that accepts a given input string of size N if it has an M sized palindrome as substring and reject if not”.
Your task here is to solve this exercise, but as we do not have compilers that can interpret TM descriptions, you instead has to code an equivalent algorithm to solve it.
Input The input will contain only one test set. You will receive two integers N and M (1≤M≤N≤5⋅105), as described above, followed by a line with a string S of size N. It is guaranteed that S contains only lowercase english letters.
Output The output must contain only one line with “Accept” (without quotes) if your Decider accepts the input or “Reject” (without quotes) if it doesn’t.
You may print every letter in any case you want (so, for example, the strings Accept, accept, ACcept and accEpT will all be recognized as a positive answer).
Examples
Input 10 4 ajabbaaksj
Output Accept
Main idea & Solution 题目问能否在给定串中找出长度为m的回文子串 先Manacher预处理，求出以每个位置为中心的最长回文串的长度； 然后依次判断即可(注意奇偶性需一致)
Code
#include <bits/stdc++.h> using namespace std; const int MX = 5e5 + 7; char s[MX],t[MX<<1]; int p[MX<<1]; bool manacher(int len,int m){ int pos = 0; t[pos++] = '$', t[pos++] = '#'; for(int i = 0;i < len;++i){ t[pos++] = s[i]; t[pos++] = '#'; } int res = 0, id = 0, mx = 0; for(int i = 1;i < pos;++i){ p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1; while(t[i + p[i]] == t[i - p[i]]) ++p[i]; if(mx < i + p[i]){ mx = i + p[i];id = i; } if((p[i] - 1) % 2 == m % 2 && p[i] - 1 >= m) return true; res = max(res,p[i]); } return false; } int main(){ int n,m; scanf("%d%d%s",&n,&m,s); if(manacher(n,m)) cout << "Accept"; else cout << "Reject"; cout << endl; }