I wrote one my problem in my blog: http://codeforces.com/blog/entry/61556 , this problem is with difficult D2B-D1A. now I will write the problem with difficult D1A(maybe this is with other difficult).
time limit: 2 seconds
memory limit: 256 megabytes
there is given a string s. the substring is named half-palindrome if we can do palindrome with change some places of characters(we can do not change this substring). find the number of substrings of s that are half-palindromes(the substring must not be empty).
the length of string is at most 100 000 and all characters are in lower-case and are one of the first 10 characters in alphabet.
example test case:
how to solve it?
I know this but I can not write that because for me is hard speak English. write in comments solution of this task. I hope you enjoyed with solving this task and this blog was usefull for you :).