Revolving Digits
Problem's Link
Mean:
给你一个字符串，你可以将该字符串的任意长度后缀截取下来然后接到最前面，让你统计所有新串中有多少种字典序小于、等于、大于原串。
analyse:
KMP的经典题。
首先我们将原串扩展成两倍，算一遍扩展KMP（自匹配），时间复杂度O(n)。
这样一来，我们就得到了eKMP[i]，eKMP[i]代表s[i...len-1]与s的最长公共子串。
为了避免重复子串重复计数，我们先求出s的最小循环节：
;i<=len;++i)
{
if(i+p[i]>=len)
{
min_cycle=len%i?len:i;
break;
}
}
{
if(i+p[i]>=len)
{
min_cycle=len%i?len:i;
break;
}
}
然后我们只需统计最小循环节以内的字符就可。
当eKMP[i]>=len时，显然是原串，E++;
否则我们只需比较一位就可判断大小，即：比较s[i+eKMP[i]]和s[eKMP[i]]的大小。
为什么只需比较一位?
因为s[0...eKMP[i]-1]和s[i...i+eKMP[i]-1]是相同的，只需判断第一个不相同的位置就可。
Time complexity: O(N)
Source code:
;
;
;
; )
p);
;
;
; )
);
);
; ;;;
;;
}
;
;
; )
p);
;
;
; )
);
);
; ;;;
;;
}