字符串专题随笔

最小循环表示法

没有找到例题，就口胡一下
记两个指针i=0,j=1,k=0记k为以i，j开头的字符串相同的最长长度为k

若s[i+k]==s[j+k] k++;
若s[i+k]>s[j+k],i=i+k+1,意味着i到i+k之间的都不可能成为最小，因为都会比j的小
若s[i+k]<s[j+k],j=j+k+1，同理

这样就做到了o(n)

---

manacher

不想说了，直接上代码 code

---