烟台建网站,wordpress重写规则,专业定制家具厂家,阿里云服务器可以做多少个网站考察字符串周期的题 题目链接
结论
要求字串 s s s的最短循环字串长就是#xff1a; a n s n − p m t [ n ] ansn-pmt[n] ansn−pmt[n] 证明如下#xff1a; 这是最大的前缀和后缀 现在我们做如下操作#xff1a; 补全字段 a a a和字段 b b b#xff0c;按子段 a a a的…考察字符串周期的题 题目链接
结论
要求字串 s s s的最短循环字串长就是 a n s n − p m t [ n ] ansn-pmt[n] ansn−pmt[n] 证明如下 这是最大的前缀和后缀 现在我们做如下操作 补全字段 a a a和字段 b b b按子段 a a a的长度人为分开并标号 上下对应相等所以1等于a 因为公共前后缀所以1等于7 … 所以红色字段是最大循环字串
ACcode
#includebits/stdc.husing namespace std;const int M 1e6 9;
int pmt[M];void get_pmt(const string p) {for (int i 1, j 0;i p.size();i) {while (j p[i] ! p[j])j pmt[j - 1];if (p[i] p[j])j;pmt[i] j;}
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n;cin n;string str;cin str;get_pmt(str);cout n - pmt[n - 1];return 0;
}
