xmuC语言程序实践week 2 大作业
算法训练 字串统计
描述
给定一个长度为n的字符串S，还有一个数字L，统计长度大于等于L的出现次数最多的子串（不同的出现可以相交），如果有多个，输出最长的，如果仍然有多个，输出第一次出现最早的。
输入
输入描述: 第一行一个数字L。 第二行是字符串S。 L大于0，且不超过S的长度。 输入样例:
输出
输出描述: 一行，题目要求的字符串。 输入样例1： 4 bbaabbaaaaa 输出样例1： bbaa 输入样例2： 2 bbaabbaaaaa 输出样例2： aa
提示
HINT:时间限制：1.0s 内存限制：512.0MB n<=60 S中所有字符都是小写英文字母。
一种思路，两种实现方式
类似KMP（字符串匹配）算法，在主串中搜索子串。区别在于，这里的子串有（），只要符合条件的子串，我们都要搜索一遍。然后统计他们出现的次数，将出现次数最多的子串输出。
思路：将子串按照长度不同分别遍历，若主串长度为n ，则
主串中长度大于等于L的子串长度 有n−L+1种，
长度为k的的种类中有n−L+k 个子串，
分别判断这些子串的重复次数。遍历时从前向后，以满足题意输出第一次出现最早的。
这里采用c++特有的stl模板库中的vector向量存
遍历完长度为k的子串，保留出现次数最多的子串和其出现次数，在全部子串枚举结束后，对不同长度子串中出现次数最多的子串再进行比较，保留所有子串中出现次数最多的子串。这里从子串长度最长的开始，以满足题意输出最长的。
1.三重循环暴力枚举
第一重循环枚举字符串长度大于等于L的，第二重循环枚举字符串起始位置，第三重循环枚举与其相同的字符串（相同指的是内容+长度）
#include<iostream>
#include<cstdio>
#define rg register
#define inf 2147483647
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define ll long long
#define maxn 5005
const double eps=1e-8;
using namespace std;
inline ll read()
{
char ch=getchar();ll s=0,w=1;
while(ch<48||ch>57){if(ch=='-')w=-1;ch=getchar();}
while(ch>=48&&ch<=57){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}
return s*w;
}
inline void write(ll x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+48);
}
int main()
{
ios::sync_with_stdio(false);
string s;
int l;
cin>>l>>s;
int max=-inf;
int len=s.length();
//cout<<len<<endl;
string v,ans;
for(int i=l;i<len;i++){
int a=len-i+1;
for(int j=0;j<a;j++){
int tmax=0;
v=s.substr(j,i);
//cout<<v<<endl;
for(int k=0;k<a;k++)
if(v==s.substr(k,i))
tmax++;
if(tmax>max || (tmax==max && v.length()>ans.length())){
ans=v;
max=tmax;
}
}
}
cout<<ans;
return 0;
}2.Stl+字符串hash
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<cstring>
#define rg register
#define inf 2147483647
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define ll long long
#define maxn 5005
const double eps=1e-8;
using namespace std;
inline ll read()
{
char ch=getchar();
ll s=0,w=1;
while(ch<48||ch>57)
{
if(ch=='-')
w=-1;
ch=getchar();
}
while(ch>=48&&ch<=57)
{
s=(s<<1)+(s<<3)+(ch^48);
ch=getchar();
}
return s*w;
}
inline void write(ll x)
{
if(x<0)
putchar('-'),x=-x;
if(x>9)
write(x/10);
putchar(x%10+48);
}
ll ans,l;
string s;
map<string,ll>p;
vector<string>v;
int main()
{
ios::sync_with_stdio(false);
cin>>l>>s;
for(rg ll i=0;i<(unsigned)s.size();i++)
{
for(rg ll j=l+i;j<=(unsigned)s.size();j++)
{
//cout<<s.substr(i,j-i)<<endl;
if((s.substr(i,j-i).size()>=l))
{
v.push_back(s.substr(i,j-i));
++p[v.back()];
}
}
}
for(rg ll i=1;i<(unsigned)v.size();i++)
{
if(p[v[i]]>p[v[ans]]||(p[v[i]]==ans&&v[i].size()>v[ans].size()))
{
ans=i;
}
}
cout<<v[ans]<<endl;
}ac记录
腾讯云开发者
