自制数据测试就出了问题。
输入:
7
abbaccac
abbac
cacaab
acc
accab
acabbbac
accabbac
本地输出+正确输出(换行省略为空格):
1 3 1 4 2 1 1
你谷IDE输出:
1 4 2 9 1 6 2
代码:
#include<cstdio>
#include<algorithm>
#include<cstring>
char str[1<<21],bstr[1<<8]={0};
int pi[1<<21]={0},len_ord[1<<8],n,ans[1<<8]={0};
int main(){
scanf("%d\n",&n),memset(ans,0,sizeof(ans));
for(int i=0;i<n;i++)len_ord[i]=i;
for(int i=0,ptr=0,c;i<n;i++){
while((c=getchar())>='a'&&c<='z')str[ptr++]=c;
bstr[i+1]=ptr;
}
std::sort(len_ord,len_ord+n,[](int x,int y){
return bstr[x+1]-bstr[x]<bstr[y+1]-bstr[y];});
for(int k=0;k<n;k++)
for(int i=bstr[k]+1,j;j=pi[i-1],i<bstr[k+1];i++){
while(j&&str[i]!=str[bstr[k]+j])j=pi[j-1];
pi[i]=j+(str[i]==str[bstr[k]+j]);
}
for(int k=0;k<n;k++)
for(int s=k;s<n;s++)
for(int i=bstr[len_ord[s]],j=0;i<bstr[len_ord[s]+1];i++){
while(j&&str[bstr[len_ord[k]]+j]!=str[i])
j=pi[bstr[len_ord[k]]+j-1];
if(str[bstr[len_ord[k]]+j]==str[i])j++;
if(j==bstr[len_ord[k]+1]-bstr[len_ord[k]])
ans[len_ord[k]]++,j=pi[bstr[len_ord[k]]+j-1];
}
for(int i=0;i<n;i++)printf("%d\n",ans[i]);
}