字符串计数

C++ 解法, 执行用时: 1ms, 内存消耗: 228KB, 提交时间: 2017-07-21

//想明白了思路就很简单，代码也很少。
//求解大于str1的字符串个数以及大于str2的字符串个数，然后两者相减就能得到处于str1和str2之间的字符串个数
//对于求解长度len在[len1,len2]之间，且字典序大于某个字符串(str)的字符串个数：
//顺序遍历(i=0:n-1)str的每个字符str[i]，则若一个字符串destr大于str，则有两种情况：
//(1)destr第i个字符大于str[i]，则之后的字符无论是什么，destr都大于str
//(2)destr第i个字符等于str[i]，则i++，并继续讨论后续字符
//最后如果len>strLen，需要考虑destr前strLen位和str完全一样，则剩余位置字符可以是任意字符。
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int getcount(char str[], int strLen, int len1, int len2){
    int count  = 0;
    for(int len = len1 ; len <= len2 ; len++){
        for(int i = 0 ;i < strLen && i < len; i++)
            count += (26 - (str[i] - 'a' + 1)) * pow(26 , strLen - i - 1 );
        if(len > strLen)
            count += pow(26 , len - strLen);
    }
    return count;
}
int main(){
    char str1[120];
    char str2[120];
    memset(str1,0,sizeof(str1));
    memset(str2,0,sizeof(str2));
    int len1, len2;
    while(cin >> str1 >> str2 >> len1 >> len2){
        int strlen1 = strlen(str1);
        int strlen2 = strlen(str2);
        int count1 = getcount(str1,strlen1,len1,len2);
        int count2 = getcount(str2,strlen2,len1,len2); 
        int count = count1 - count2 - 1;
        cout << count << endl;
    }
    return 0;
}

C 解法, 执行用时: 1ms, 内存消耗: 368KB, 提交时间: 2021-04-03

#include<stdio.h>
#include<string.h>
#include<math.h>
int main()
{
    char ch1[100]={'\0'};
    char ch2[100]={'\0'};
    int a,b;
    while(scanf("%s%s%d%d",&ch1,&ch2,&a,&b)!=EOF){
        int m=0,n=0,s=0,num=0;
        m=strlen(ch1);
        n=strlen(ch2);
        s=strcmp(ch1,ch2);
     if(s<0){
             
            if(m>=a&&b<=n){
                num=1;
                for(int i=0;i<b;i++)
                {
                    num=num+(ch2[i]-ch1[i])*pow(26,b-i-1);
                }
              printf("%d\n",num-2);
            }
            if(a>m&&b<=n){
                num=1;
                for(int j=a-1;j<b;j++)
                {
                    num+=(26^(b-j-1))*(ch2[j]-ch1[j]);
                }
             printf("%d\n",num);
        }
        }
        if(s=0)
        {
            num=1;
            printf("%d\n",num);
        }
    }
    return 0;
}

C 解法, 执行用时: 1ms, 内存消耗: 368KB, 提交时间: 2020-08-11

#include<stdio.h>
//#include<conio.h>
#include<string.h>
#include<math.h>
int main()
{
    char ch1[100]={'\0'};
    char ch2[100]={'\0'};
    int a,b;
    //gets(ch1);
    //gets(ch2);
    while(scanf("%s%s%d%d",&ch1,&ch2,&a,&b)!=EOF){
        int m=0,n=0,s=0,num=0;
        m=strlen(ch1);
        n=strlen(ch2);
        s=strcmp(ch1,ch2);
       // printf("%d%d%d",m,n,s);
       
     if(s<0){
             
            if(m>=a&&b<=n){
                num=1;
                for(int i=0;i<b;i++)
                {
                    //printf("%d\n",ch2[i]-ch1[i]);
                     
                    num=num+(ch2[i]-ch1[i])*pow(26,b-i-1);
                     // printf("%d\n",num);
                }
              printf("%d\n",num-2);
 
            }
            if(a>m&&b<=n){
                num=1;
                for(int j=a-1;j<b;j++)
                {
                    num+=(26^(b-j-1))*(ch2[j]-ch1[j]);
                }
             
             printf("%d\n",num);
        }
        }
        if(s=0)
        {
            num=1;
            printf("%d\n",num);
        }
        
    }
    return 0;
}

C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2021-06-12

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
 
int main()
{
    string s1,s2;
    int len1,len2;
    while(cin>>s1>>s2>>len1>>len2)
    {
        s1.append(len2-s1.size(),'a');
        s2.append(len2-s2.size(),(char)('z'+1));
        //计算两个字符串之间的差值
        vector<int> tmp;
        for(int i=0;i<len2;++i)
        {
            tmp.push_back(s2[i]-s1[i]);
        }
        //计算两者之间的数目
        long long ret=0;
        for(int i=len1;i<=len2;++i)
        {
            for(int j=0;j<i;++j)
            {
                ret+=tmp[j]*pow(26,i-1-j);
            }
        }
        //不包含s2
        cout<<ret-1<<endl;
        
        
    }
    return 0;
}

C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2021-05-08

#include<iostream>
#include<string>
using namespace std;
  
int main(){
    string s1,s2;
    int len1,len2;
    while(cin>>s1>>s2>>len1>>len2){
        int result = 0;
        int dp[120];
        for(int i=1; i<=len2; i++){
            dp[i] = (26*(dp[i-1]))%1000007;
            if(i<=s1.size()) dp[i] -= s1[i-1];
            if(i<=s2.size()) dp[i] += s2[i-1];
            if(i == s2.size()) dp[i]--;
            if(i>=len1) result += dp[i];
        }
        cout<<result%1000007<<endl;
    }
    return 0;
}
/*#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
using namespace std;
int main(){
    string s1,s2;
    int len1,len2;
    int array[len2-len1+1];
    int num;
    while(cin>>s1>>s2>>len1>>len2){
    for(int i=len1;i<=len2;i++){
        array[i-len1]=s2[i]-s1[i];
    }
    for(int j=0;j<len2-len1+1;j++){
        num+=array[j]*pow(26,j);
    }
    return num;
        }
}*/

详情