I can't understand this code, please explain to me what is happening in the second line of the for loop.
#include <cstdio>
char s[5005000];
int h[5005000];
const int M=3;
int main() {
scanf("%s",s);
int a=0,b=0,p=1,v=0;
for(int i=0;s[i];++i){
a=a*M+s[i],b+=s[i]*p,p*=M;
if(a==b)v+=(h[i+1]=h[(i+1)>>1]+1);
}
printf("%d\n",v);
return 0;
}
It checks if the string in [0, i] interval is palindrome or not by using ASCII
for example if the string is a2a
---------------------------
i = 0
---------------------------
a = a * M + str[0] = 97
b += str[0] * p = 97
p * = M -> p = 3
Since a == b then h[1] = h[1>>1] + 1 = 1 and v += h[1], therefore v = 1
---------------------------
i = 1
---------------------------
a = a * M + str[1] = 97*3 + 50 = 341
b += str[1] * p = 97 + 50*3 = 247
p * = M -> p = 9
Since a != b then nothing happens
---------------------------
i = 2
---------------------------
a = a * M + str[2] = 341*3 + 97 = 1120
b += str[2]*p = 247 + 97*9 = 1120
p *= M -> p = 27
Since a == b then h[3] = h[3>>1] + 1 = 2 and v += h[3], therefore v = 3
---------------------------
Finally, v = 3