【集训Day2】字符串
程序员文章站
2022-07-14 19:03:12
...
字符串(string)
【问题描述】
给一个字符串T,问在字符串T 中可以包含最多多少个不重叠的字符串S。
字符串中的每个字符为小写或者大写字母。
【输入格式】
第一行输入一个字符串S。
第二行输入一个字符串T。
【输出格式】
输出一行,包括一个整数表示答案。
【输入样例】
Aba
Abababa
【输出样例】
2
【数据范围】
50%的数据,1<=字符串T 长度<=20000, 1<=字符串S 长度<=100
100%的数据,1<=字符串T 长度<=1000000, 1<=字符串S 长度<=100000。其中多数是随
机产生。
【解题思路】
将字符串转化为独一无二的五十二进制数,利用部分和原理一段一段进行比较。
【参考程序】
#include<iostream>
#include<cstdio>
using namespace std;
const int mod=13131313;//取模是因为五十二进制数通常非常大。
string s,t;
int lens,lent;
long long num,l[1000001],tmp,ans;
int trans(char a)//将字母变成五十二进制中的0...51
{
if (a>='a') return a-'a';
else return a-'A'+26;
}
int main()
{
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
cin>>s;lens=s.size();
for (int i=0;i<lens;i++)
num=(num*52%mod+trans(s[i]))%mod;//转化出s的五十二进制代码
cin>>t;lent=t.size();
l[1]=(l[0]*52%mod+trans(t[0]))%mod;//转化出1~t[i]的五十二进制代码
for (int i=1;i<lent;i++)
l[i+1]=(l[i]*52%mod+trans(t[i]))%mod;
tmp=1;
for (int i=0;i<lens;i++)//利用部分和原理
tmp=tmp*52%mod;
//像是如果要取999666中的666,需要999666- 999*10^2。
//这里求的就是其中的对应10^2,只不过这里是52^lens
int left=1;
while (left<=lent-lens+1)
{
long long find=(l[left+lens-1]-l[left-1]*tmp%mod+mod)%mod;
if (find==num)
{
ans++;
left+=lens;//不重叠
}
else left++;
}
cout<<ans;
return 0;
}
上一篇: Python学习 DAY 4
下一篇: day2:字符串问题总结