2020-2021:teams:legal_string:jxm2001:字符串_1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:字符串_1 [2020/08/27 11:22] jxm2001 |
2020-2021:teams:legal_string:jxm2001:字符串_1 [2020/08/27 11:38] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 379: | 行 379: | ||
| == 题解 1 == | == 题解 1 == | ||
| + | 考虑求出每个位置的 $z$ 函数，统计每个前缀出现次数。关于 $z$ 函数统计前缀次数，如果 $s[l,r]=s[1,r-l+1]$，显然有 $s[l,r-1]=s[1,r-l]$。 | ||
| + | 于是可以直接用桶维护 $z$ 函数，然后求后缀和。 | ||
| + | |||
| + | 然后从大到小枚举每个与前缀相同的后缀并记录答案，判定条件为 $i+z(i)-1=n$。时间复杂度 $O(|S|)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=1e5+5; | ||
| + | namespace KMP{ | ||
| + | int z[MAXN]; | ||
| + | void get_z(char *s,int n){ | ||
| + | z[1]=n; | ||
| + | _rep(i,2,n)z[i]=0; | ||
| + | for(int i=2,l=0,r=0;i<=n;i++){ | ||
| + | if(i<=r)z[i]=min(z[i-l+1],r-i+1); | ||
| + | while(i+z[i]<=n&&s[z[i]+1]==s[i+z[i]])z[i]++; | ||
| + | if(i+z[i]-1>r)l=i,r=i+z[i]-1; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | int c[MAXN]; | ||
| + | char s[MAXN]; | ||
| + | int main() | ||
| + | { | ||
| + | gets(s+1); | ||
| + | int n=strlen(s+1); | ||
| + | KMP::get_z(s,n); | ||
| + | stack<int> s; | ||
| + | _rep(i,1,n){ | ||
| + | if(i+KMP::z[i]-1==n) | ||
| + | s.push(KMP::z[i]); | ||
| + | c[KMP::z[i]]++; | ||
| + | } | ||
| + | for(int i=n;i;i--)c[i-1]+=c[i]; | ||
| + | enter(s.size()); | ||
| + | while(!s.empty()){ | ||
| + | printf("%d %d\n",s.top(),c[s.top()]); | ||
| + | s.pop(); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| == 题解 2 == | == 题解 2 == | ||
| - | 考虑求出每个位置的 $f$ 函数，统计前缀出现次数。 | + | 考虑求出每个位置的 $f$ 函数，统计每个前缀出现次数。 |
| - | 然后从大到小枚举每个与前缀相同的后缀并记录答案，初始为 $f(n)$，然后不断迭代 $f$ 即可。时间复杂度 $O(|S|)$。 | + | 然后从大到小枚举每个与前缀相同的后缀并记录答案，初始为 $n$，然后不断迭代 $f$ 即可。时间复杂度 $O(|S|)$。 |
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <code cpp> | ||
| - | const int MAXN=1e6+5; | + | const int MAXN=1e5+5; |
| namespace KMP{ | namespace KMP{ | ||
| int f[MAXN]; | int f[MAXN]; | ||
| 行 403: | 行 446: | ||
| } | } | ||
| char s[MAXN]; | char s[MAXN]; | ||
| - | LL c[MAXN]; | + | int c[MAXN]; |
| int main() | int main() | ||
| { | { | ||
| 行 410: | 行 453: | ||
| KMP::get_f(s,n); | KMP::get_f(s,n); | ||
| _rep(i,1,n)c[KMP::f[i]]++; | _rep(i,1,n)c[KMP::f[i]]++; | ||
| - | LL ans=0; | + | stack<pair<int,int> >pt; |
| - | stack<pair<int,LL> >pt; | + | |
| for(int i=n;i;i--)c[KMP::f[i]]+=c[i]; | for(int i=n;i;i--)c[KMP::f[i]]+=c[i]; | ||
| for(int i=n;i;i=KMP::f[i]) | for(int i=n;i;i=KMP::f[i]) | ||
| 行 417: | 行 459: | ||
| enter(pt.size()); | enter(pt.size()); | ||
| while(!pt.empty()){ | while(!pt.empty()){ | ||
| - | printf("%d %lld\n",pt.top().first,pt.top().second); | + | printf("%d %d\n",pt.top().first,pt.top().second); |
| pt.pop(); | pt.pop(); | ||
| } | } | ||
2020-2021/teams/legal_string/jxm2001/字符串_1.1598498539.txt.gz · 最后更改: 2020/08/27 11:22 由 jxm2001
