题目大意：
求一个子串，子串既是前缀又是后缀。
然后再求出它在整个串中出现的次数。
思路分析：
能够非常easy想到怎样推断一个串既是前缀又是后缀。
仅仅须要它与 sa【0】 的lcp 等于 整个串的长度减去它的 sa 值。
然后接下来的工作是推断出现了 多少次。
首先我们想到，假设这个子串是目标前后缀。
那么出现过它的子串在sa 中的下标一定比这个串大。
由于它已经是最简的了。
然后能够直接二分求出他出现了多少次。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define maxn 300005
#define debug puts("here!")
using namespace std;
char str[maxn];
int sa[maxn],t1[maxn],t2[maxn],c[maxn],n;
void suffix(int m)
{
int *x=t1,*y=t2;
for(int i=0; i<m; i++)c[i]=0;
for(int i=0; i<n; i++)c[x[i]=str[i]]++;
for(int i=1; i<m; i++)c[i]+=c[i-1];
for(int i=n-1; i>=0; i--)sa[--c[x[i]]]=i;
for(int k=1; k<=n; k<<=1)
{
int p=0;
for(int i=n-k; i<n; i++)y[p++]=i;
for(int i=0; i<n; i++)if(sa[i]>=k)y[p++]=sa[i]-k;
for(int i=0; i<m; i++)c[i]=0;
for(int i=0; i<n; i++)c[x[y[i]]]++;
for(int i=0; i<m; i++)c[i]+=c[i-1];
for(int i=n-1; i>=0; i--)sa[--c[x[y[i]]]]=y[i];
swap(x,y);
p=1;
x[sa[0]]=0;
for(int i=1; i<n; i++)
x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
if(p>=n)break;
m=p;
}
}
int rank[maxn],height[maxn];
void getheight()
{
int k=0;
for(int i=0; i<n; i++)rank[sa[i]]=i;
for(int i=0; i<n; i++)
{
if(k)k--;
if(!rank[i])continue;
int j=sa[rank[i]-1];
while(str[i+k]==str[j+k])k++;
height[rank[i]]=k;
}
}
int cnt[maxn];
int vis[maxn];
int f[maxn][30];
void RMQINIT()
{
for(int i=0;i<n;i++)
f[i][0]=height[i];
for(int j=1;(1<<j)<=n;j++)
for(int i=0;i+(1<<j)-1<n;i++)
f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
int RMQ(int l,int r)
{
if(l==r)return n-1-sa[l];
if(l>r)swap(l,r);
l++;
int k=floor(log(r-l+1.0)/log(2.0));
return min(f[l][k],f[r+1-(1<<k)][k]);
}
struct node
{
int len,time;
}fans[maxn];
int top=0;
void solve()
{
RMQINIT();
for(int i=1;i<n;i++)
{
int l,r;
if( i<rank[0] )
l=i,r=rank[0];
else if(i>rank[0]) l=rank[0],r=i;
else continue;
int comlen=RMQ(l,r);
if( sa[i] + comlen == n-1 )
{
int L=i,R=n-1,ans;
while(L<=R)
{
int mid=(L+R)>>1;
if(RMQ(i,mid)>=comlen)
{
ans=mid;
L=mid+1;
}
else R=mid-1;
}
fans[top].len=comlen;
fans[top++].time=ans-i+1;
}
}
fans[top].len=n-1;
fans[top++].time=1;
printf("%d
",top);
for(int i=0;i<top;i++)
printf("%d %d
",fans[i].len,fans[i].time);
}
int main()
{
scanf("%s",str);
n=strlen(str);
str[n]=0;
n++;
suffix(128);
getheight();
solve();
return 0;
}
理解KMP求前缀。。
。简直diao
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define maxn 100005
using namespace std;
int next[maxn];
char str[maxn];
void getnext(int len)
{
next[0]=0;next[1]=0;
for(int i=1;i<len;i++)
{
int j=next[i];
while(j && str[j]!=str[i])j=next[j];
next[i+1]=str[j]==str[i]?j+1:0;
}
}
struct node
{
int len;
int time;
bool operator < (const node &cmp)const
{
return len<cmp.len;
}
}fans[maxn];
int top=0;
int cnt[maxn];
void solve(int n)
{
int j=n;
for(int i=0;i<=n;i++)
cnt[i]=1;
for(int i=n;i>=1;i--)
{
int j=i;
if(next[j])
cnt[next[j]]+=cnt[j];
}
j=next[n];
while(j)
{
fans[top].len=j;
fans[top++].time=cnt[j];
j=next[j];
}
sort(fans,fans+top);
printf("%d
",top+1);
for(int i=0;i<top;i++)
printf("%d %d
",fans[i].len,fans[i].time);
printf("%d %d
",n,1);
}
int main()
{
scanf("%s",str);
int n=strlen(str);
getnext(n);
solve(n);
return 0;
}