ICPC Pacific Northwest Regional Contest 2017 A Odd Palindrome

ICPC Pacific Northwest Regional Contest 2017 A Odd Palindrome

​​We say that a string is oddodd if and only if all palindromic substrings of the string have odd length.

Given a string ss, determine if it is oddodd or not.

A substring of a string ss is a nonempty sequence of consecutive characters from ss. A palindromic substring is a substring that reads the same forwards and backwards.

1 Input

The input consists of a single line containing the string ss (1 ≤ |s| ≤ 100)(1≤∣s∣≤100).

It is guaranteed that ss consists of lowercase ASCIIASCII letters (‘a’–‘z’)(‘a’–‘z’) only.

2 Output

If ss is oddodd, then print “Odd.Odd.” on a single line (without quotation marks). Otherwise, print “Or\ not.Or not.” on a single line (without quotation marks).

样例输入复制 1 2 3 4 amanaplanacanalpanama madamimadam annamyfriend nopalindromes 样例输出复制 1 2 3 4 Odd. Odd. Or not. Odd. 用manacher找出所有回文串的长度，判断下是否是奇数即可

#includeusing namespace std;char s[110],a[2200];int p[220];int main(){ freopen("a.in","r",stdin); while(~scanf("%s",s)){ int n=strlen(s); for (int i=1;i<=n;++i) a[(i<<1)]=s[i-1],a[(i<<1)-1]='#'; n<<=1;++n;a[n]='#'; int mx=0,id=0,ans=0;bool flag=1; for (int i=1;i<=n;++i){ if (i+p[i]0&&i+p[i]<=n) ++p[i]; if (i+p[i]>mx) mx=i+p[i],id=i; if (p[i]==1) continue; if (!((p[i]-1)%2)) flag=0; } if (flag) puts("Odd.");else puts("Or not."); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。