Search code examples
c++palindrome

Can't understand shorthand code in palindrome


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;
}

Solution

  • 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