Problem D: String
Description
給定一個字符串S[1..n]和一個整數(shù)T，現(xiàn)在需要在字符串S中找出長度不小于T的一個子串，使得其在原串中不重疊出現(xiàn)的次數(shù)最多，求這個次數(shù)。
Input
第一行：一個整數(shù)T(T > 1)
第二行：一個字符串S，且僅包含小寫字母，字符串長度不超過10000
Output
一個整數(shù)。代表出現(xiàn)最多的次數(shù)
如果沒有滿足條件的解則輸出0
Sample Input
2
ababab
Sample Output
3
類似最大重復子串，可以用后綴數(shù)組+貪心或者后綴樹。由于這題數(shù)據(jù)量比較小，直接枚舉。
#include <iostream>
const int N = 10001;
int t,len;
char str[N];
int query(int from,int to)
{
int i=0,j,k,ans=0;
while(i<len){
for(j=i,k=from;j<len && k<=to;j++,k++)
if(str[j]!=str[k])
break;
if(k>to)
ans++,i=j;
else
i++;
}
return ans;
}
int solve(){
int i,j,ans=0,n;
if(t>len) return 0;
for(i=0,j=t-1;j<len;i++,j++)
if((n=query(i,j))>ans)
ans=n;
return (ans==1)? 0:ans;
}
int main(){
while(scanf("%d",&t)!=EOF){
scanf("%s",str);
len=strlen(str);
printf("%d\n",solve());
}
return 0;
}