解题思路
Trie树存一下子串就行了,一开始用map被卡了两个点
代码
#include<bits/stdc++.h>
using namespace std;
string s,ss;
int l,k,tot,ans;
int tree[1000010][11],e[1000010];
void insert(string s)
{
int p=0;
for(int i=0;i<k;i++)
{
int c=s[i]-'A';
if(!tree[p][c])tree[p][c]=++tot;
p=tree[p][c];
}
e[p]++;
ans=max(ans,e[p]);
}
int main(){
freopen("dna.in","r",stdin);
freopen("dna.out","w",stdout);
getline(cin,s);
l=s.size();
scanf("%d",&k);
for(int i=0;i+k-1<l;i++)
{
ss=s.substr(i,k);
insert(ss);
}
printf("%d",ans);
}