The suffix of string s of length l (1?≤?l?≤?|s|) is
string s[|s|?-?l?+?1..|s|].
Your task is, for any prefix of string s which matches a suffix of string s,
print the number of times it occurs in strings as a substring.
Input
The single line contains a sequence of characters s1s2...s|s| (1?≤?|s|?≤?105) —
string s. The string only consists of uppercase English letters.
Output
In the first line, print integer k (0?≤?k?≤?|s|) —
the number of prefixes that match a suffix of string s. Next print klines,
in each line print two integers li ci.
Numbers li ci mean
that the prefix of the length li matches
the suffix of length li and
occurs in string s as a substring ci times.
Print pairs li ci in
the order of increasing li.
Sample test(s)
input
ABACABA
output
3
1 4
3 2
7 1
input
AAA
output
3
1 3
2 2
3 1
題意：
給你一個長度不超過10^5的字符串。要你按長度輸出和後綴完全匹配的的前綴的長度。和該前綴在整個串中出現的次數。（可重疊）
思路：
比賽時一看到前綴後綴。心裡一陣竊喜。哈哈。剛好學過後綴數組。正好有用武只地了，一番思索後算法已成型。0號後綴就是整個字符串。 和它求公共前綴能和整個後綴匹配的後綴一定有一個前綴能和這個後綴完全匹配。 然後再確定出現了多少次。 當你知道某個後綴是目標後綴時。 你可以知道到它的rank值。 然後要完全包含一個後綴的後綴一定在它後面。 根據排名規則。 你想啊。如果後綴a的前綴包含後綴b。a還會排在b前面嗎？ 明顯長度短的排前面了。 所以剩下工作就是確定可以向下擴展的最大距離了。
這個可以根據height數據的值確定。 要用到二分+rmq。二分確定位置。rmq判斷是否滿足條件。思路雖然正確但是到比賽結束都一直是錯的，到後面調試出來才知道還是對後綴數組的理解不夠深刻。問題就出在倍增算法為什麼要規定txt[n-1]=0.還有j=sa[rank[i]-1];rank[i]=0怎麼處理。我們把原來的字符串末尾加個0就可解決。詳細見代碼：
#include
using namespace std;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const double PI=acos(-1.0);
const int maxn=150010;
char txt[maxn];
int sa[maxn],T1[maxn],T2[maxn],ct[maxn],he[maxn],rk[maxn],ans,n,m;//sa[i]表示排名第i的後綴的起始位置。
int rmq[25][maxn],lg[maxn],ansn[maxn],ansp[maxn],ptr;
void getsa(char *st)//注意m為ASCII碼的范圍
{
int i,k,p,*x=T1,*y=T2;
for(i=0; i=0; i--)//倒著枚舉保證相對順序
sa[--ct[x[i]]]=i;
for(k=1,p=1; p=k) y[p++]=sa[i]-k;//按第二關鍵字排序.y[i]表示第二關鍵字排名第i的後綴起始位置
for(i=0; i=0; i--) sa[--ct[x[y[i]]]]=y[i];//接著按第一關鍵字排序
for(swap(x,y),p=1,x[sa[0]]=0,i=1; i>1]+1;
}
void solve()
{
int low,hi,mid,p,pos,a,b,ans,tp,i;
getsa(txt),gethe(txt),rmq_init();
ptr=0,pos=rk[0];
for(i=n-2;i>0;i--)
{
if(rk[i]=n-i-1)
{
ansp[ptr]=p,tp=rk[i]+1;
low=rk[i]+1,hi=n-1,ans=-1;
while(low<=hi)
{
mid=(low+hi)>>1;
if(rmq_min(tp,mid)>=p)
ans=mid,low=mid+1;
else
hi=mid-1;
}
ansn[ptr++]=ans-rk[i]+1;
}
}
}
int main()
{
int i;
prermq();
while(~scanf("%s",txt))
{
m=150,n=strlen(txt);
n++;
solve();
ansp[ptr]=n-1;
ansn[ptr++]=1;
printf("%d\n",ptr);
for(i=0;i
接下來是第二種思路。比賽完後。第一個思路調不出來。於是就去群裡問了下。結果被叉姐鄙視了。扔了句kmp就走了。定神一想是啊。自己智商被深深得鄙視了。kmp可以很輕松得統計出每個前綴在原串中出現的次數。具體做法是對原串求個失配數組。然後自己和自己匹配。若第i個位置和第j個位置匹配了說明前綴j在第i個位置出現了一次。我們用cnt[i]記錄。前綴i出現的次數。最後統計cnt[next[i]]+=cnt[i]。這個很好理解。如果前綴j能在i這個位置出現一次那麼next[j]一定能在i這個位置出現一次。統計完每個前綴在原串中出現次數後。現在就要找錢綴和後綴匹配的前綴的個數了。這個很簡單。自己和自己匹配不就是拿自己的前半部分和自己的其他部分匹配麼。所以我們只需要匹配第n+1個位置就可以找出所有和後綴匹配的前綴了。華麗的O(n)就過掉了。。。。
詳細見代碼：
#include
using namespace std;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const double PI=acos(-1.0);
const int maxn=150010;
char txt[maxn];
int f[maxn],cnt[maxn],ansp[maxn],ansn[maxn],ct,n;
void getf(char *p)
{
int i,j;
f[0]=f[1]=0;
for(i=1;i0;j--)//為什麼可以這樣做呢。終點不同的串一定是不同的串。kmp保證了終點不同。
if(f[j])//f[j]表示下個比較的位置。說明前f[j]-1一定是相同的。
cnt[f[j]-1]+=cnt[j-1];
while(t)//前綴匹配後綴
{
ansp[ct]=t;
ansn[ct++]=cnt[t-1];
t=f[t];
}
printf("%d\n",ct);
for(i=ct-1;i>=0;i--)
printf("%d %d\n",ansp[i],ansn[i]);
}
int main()
{
while(~scanf("%s",txt))
{
n=strlen(txt);
memset(cnt,0,sizeof cnt);
getf(txt);
KMP();
}
}
