欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【集训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;
}
相关标签: 字符串