字符串计数

/*看了之前50多个答案，发现大部分都是错误的，根据自己对题目的理解，给出了以下思路，目前
我还没有找到bug，欢迎牛友们检查，如有bug，我继续修改，答题思路是对的*/
/*首先是从之前的几个测试样例分析，其中一个为 str1 = cpqejrrgp, str2 = cpqejtrdg, 
len1 = 9, len2 = 9，设所求满足情况的字符串代号为 str（str有35064种）。
第一步：首先找到两个字符串相对应位置的第一个不相等的位置，即若ab 和 ce,
第一个相对位置不相等的为值就是下标为0的地方 a 和 c 不一样，str1和str2中第一个相对不相等
的位置是下标为5的地方，即 r 和 t，设下标为k；
第二步：先求在此下标处，字符处于下标位置字符之间的情况，即str[k]>str1[k] && str[k]<str2[k]
的情况，这个最好算，只要k位置大于str1小于str2对应的k位置，后面的任一位置可以随意取，每个
位置有26种，例如str1[5]和str2[5]之间共有num1种（‘t’-'r'-1=1种即为's'这一种情况），
str[5]为s的时候，后面三位可以随意取；共有(str2[k] - str1[k] - 1)*pow(26, i - k)种，
其中i为len1到len2之间的取值，这里用一个for循环累加；
第三步：其次再求str[k]==str1[k]时有多少种，此时，str[k+1]需大于str1[k+1],k+2位，k+3位...
可以随意取，接着再求str[k]==str1[k]&&str[k+1]==str1[k+1]的情况，需str[k+2]大于str1[k+2]
，k+3以及之后的位置随意取，以此类推，直到算到k==len2-1的位置为止;
第四步：最后求str[k]==str2[k]的情况，此时，str[k+1]需要小于str2[k+1],k+2，k+3等之后的
位置随意取，接着再求str[k]==str2[k]&&str[k+1]==str2[k+1]的情况，需要str[k+2]小于str2[k+2],
后面的位置随意取，以此类推，直到算到k==len2-1的位置为止；
第五步：把所有情况相加，注意还有几处边界位置需要处理，具体参考以下代码
*/
#include<iostream>
#include<string>
#include<math.h>
using namespace std;
int main()
{
    string str1,str2;
    int len1,len2;
    while(cin>>str1>>str2>>len1>>len2)
    {
         if(str1.length()<len2)
             str1.append(len2-str1.length(),'a'-1);
          if(str2.length()<len2)
              str2.append(len2-str2.length(),'z'+1);
          long long sum = 0;
          int k = 0;
          //第一步，找第一个相对位置不相等的位置下标
          while(str1[k]==str2[k])
          {
                k++;
          }
          if(str1[k]<str2[k] && len1<=len2)
          {
                //第二步，计算str[k]>str1[k] && str[k]<str2[k]的情况
                for(int i= len1-1;i<len2;i++)
                {
                     if(i==k)
                     {
                         if(k==len1-1 && k==len2-1)
                              sum += str2[k] - str1[k] -1;
                         else
                              sum += str2[k] - str1[k];
                     }
                     else
                            sum += (str2[k] - str1[k] - 1)*pow(26,i-k);
                }
                k++;
                //第三步，计算str[k]==str1[k]时的情况和str[k]==str2[k]的情况
                for(int i = len1;i <= len2;i++)
                {  for(int j=k;j<i;j++)
                        sum += ('z'-str1[j])*pow(26,i-j-1);
                    for(int j=k;j<i;j++)
                        sum += (str2[j]-'a')*pow(26,i-j-1);
                }
          }
          cout << sum << endl;//我这里没有对1000007取模，答案也是能过的，牛友们可自行添加
    }
    system("pause");
    return 0;
}

import java.util.Scanner;

/**
 * 例如ab ce 1 2
 * 过程分为以下几个阶段：
 * 第一阶段：i=min=1;b c,sum=2;除开首字母(剩下只有i-1=0个字母)
 * 第二阶段：i=max=2;ac ... az ,ba ... bz ,ca ,cb;sum = 2+26*2=54;
 * 第三阶段：i=max=2;c d e(除开首字母(剩下只有i-1=1个字母)，
             判断大于b小于等于e的字符串个数);sum = 54+3=57;
 * 第四阶段：减去等于ce这个不满足的条件。sum = 57-1 = 56;
 * 		      注意：仅最后一个小于等于e这个条件需要减去，
          例如abc bbc 1 3 ,i=2时，ac ... az,ba,bb这里这个bb不需要排除，因为bb<bbc
 * 			  
 */
public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		while (scan.hasNext()) {
			String s = scan.nextLine();
			String[] array = s.split(" ");
		
			int min = Integer.parseInt(array[2]);
			int max = Integer.parseInt(array[3]);
			char[] ar = array[0].toCharArray();
			char[] br = array[1].toCharArray();
			long sum = 0;
			for (int i = min; i <= max; i++) {
				char a=ar[0];
                char b=br[0];
               sum  += (long)Math.pow(26,i-1)*(b-a);
                long suma = 0;
    			long sumb = 0;
				for (int j = 1; j < ar.length; j++)// 找到比ar剩余字符串小的字符串个数
				{
					suma = suma + (ar[j] - 'a') * (long) Math.pow(26, i- 1 - j);
				}
				for (int j = 1; j < br.length; j++)// 找到比br剩余字符串小的字符串个数
				{
					sumb = sumb + (br[j] - 'a') * (long) Math.pow(26, i - 1 - j);
				}
			
				sum = sum + sumb-suma;
			}
			sum--;
			System.out.println(sum % 1000007);
		}

	}

}

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
const int mod = 1000007;
int dp1[100010], dp2[100010];
char s1[110], s2[110];
int  l1, l2;

int main() {

    while(scanf("%s %s %d %d", s1, s2, &l1, &l2) != EOF) {
    memset(dp1, false, sizeof(dp1));
    memset(dp2, false, sizeof(dp2));
    int n1 = strlen(s1);
    int n2 = strlen(s2);
    dp1[0] = 1;
    dp2[0] = 1;
    for(int i = 1; i <= l2; ++i) {
        if(i < n1) {
            dp1[i] = ((dp1[i-1]-1)*26 + (s1[i-1]-'a'+1)) % mod;
        } else if(i == n1) {
            dp1[i] = ((dp1[i-1]-1)*26 + (s1[i-1]-'a')) % mod;
        } else {
            dp1[i] = dp1[i-1]*26%mod;
        }
        if(i < n2) {
            dp2[i] = ((dp2[i-1]-1)*26 + (s2[i-1]-'a'+1)) % mod;
        } else if(i == n2) {
            dp2[i] = ((dp2[i-1]-1)*26 + (s2[i-1]-'a')) % mod;
        } else {
            dp2[i] = dp2[i-1]*26%mod;
        }
    }
    int sum1 = 0, sum2 = 0, ans;
    for(int i = l1; i <= l2; ++i) {
        sum1 += dp1[i];
        sum1 %= mod;
        sum2 += dp2[i];
        sum2 %= mod;
    }
    ans = sum2 - sum1;
    if(l2 >= n1) ans--;
    printf("%d\n", (ans%mod+mod)%mod);
    }
    return 0;
}

计算比字符串s1大的len1~len2字符串个数 - 比s2大的len1~len2字符串个数即为在两个字符串中的个数。
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <math.h>
int calsubstring(int len1,int len2){
	int rt = 0;
	rt = pow(26,len1) * (pow(26, len2 - len1 + 1)-1)/25;
	return rt;
}
int calbigger(char* str,int strLen,int len1,int len2){
	int count = 0;
	int tail = (len2 - strLen) > 0 ? strLen -1: len2 - 1;
	if (len2 > strLen)
	{
		count += calsubstring(1, len2 - strLen);
	}
	for (int i = tail; i >= 0;i--)
	{
		int start = (i + 1 - len1) > 0 ? 0 : len1 - (i + 1);
		count += ('z' - str[i])*calsubstring(start, len2 - i-1);
	}
	return count;
}
int main(){
	int len1 = 0, len2 = 0;
	char str1[110] = { 0 };
	char str2[110] = { 0 };
	while (scanf("%s %s %d %d",str1,str2,&len1,&len2)!=EOF){
		int str_len1 = strlen(str1);
		int str_len2 = strlen(str2);
		int rt = calbigger(str1, str_len1, len1, len2) - calbigger(str2, str_len1, len1, len2);
		
		printf("%d\n", rt-1);
	}
	return 0;
}

# include<bits/stdc++.h>

using namespace std;

int main()
{     string s1,s2;     int l1,l2;     while(cin>>s1>>s2>>l1>>l2)      {         s1.append(l2-s1.length(), 'a');         s2.append(l2-s2.length(), (char)('z'+1));         vector<int> v;         for(int i=0;i<l2;i++)             v.push_back(s2[i]-s1[i]);         int result = 0;         for(int i=l1;i<=l2;i++)             for(int j=0;j<i;j++)                 result += v[j]*pow(26,i-1-j);                  cout<<result-1<<endl;     }     return 0;
}

/*
题目描述
    求字典序在s1和s2之间的，长度在len1到len2的字符串的个数，结果mod 1000007。
输入描述:
    每组数据包涵s1（长度小于100），s2（长度小于100），len1（小于100000），len2（大于len1，小于100000）
输出描述:
    输出答案。
示例1
输入
    ab ce 1 2
输出
    56
思路
    采用27进制的想法，位数不足补'a'-1,位数超出则截取
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
#define N 1000007
int main(){
    string s1,s2;
    int l1,l2;
    while(cin>>s1>>s2>>l1>>l2){
        string temp;
        if(s1>s2){
            temp=s1;
            s1=s2;
            s2=temp;
        }
        if(s1.length()<l2)
            s1.append(l2-s1.length(),'a'-1);
        else
            s1=s1.substr(0,l2);
        if(s2.length()<l2)
            s2.append(l2-s2.length(),'a'-1);
        else
            s2=s2.substr(0,l2);
        int a[l2];
        for(int i=0;i<l2;i++){
            a[i]=s2[i]-s1[i];
        }
        int res=0;
        for(int i=0;i<=l2-l1;i++){
            for(int j=0;j<l2-i;j++)
            {
                double t=a[j]*pow(26,l2-i-j-1);
                res+=t;
                if(res>=N)
                    res=res%N;
            }
        }
        cout<<res-1<<endl;
    }
    return 0;
}

	

//完美版，牛客答案有漏洞不妨自测程序 az b 1 2 看是否等于0 ab c 1 2看是否等于51.
//看了其他回答，基本百分之80都有漏洞。
#include<iostream>
#include<string>
#include<math.h>
using namespace std;
int main(){
    string str1,str2;
    int len1,len2;
    while( cin >> str1 >> str2 >> len1 >> len2 ){
        int i,j,l1,l2,num = 0;
        char bb = 96;
        if(str1.length() < len2 )
            str1.append(len2 - str1.size(),bb);
        if(str2.length() < len2 )
            str2.append(len2 - str2.size(),bb);
        for(i=len1;i<=len2;i++)
            for(j=0;j<i;j++)
        	    num = num + (str2[j] - str1[j])*pow(26,i-j-1);
        cout << num-1 <<endl;
    }
}

def gc(i, A):
    return ord(A[i]) if i < len(A) else 96

while 1:
    try:
        s = raw_input()
    except:
        break
    s1, s2, l1, l2 = s.split(' ')
    d, s, l1, l2 = 0, 0, int(l1), int(l2)
    for i in range(l2):
        a, b = gc(i, s1), gc(i, s2)
        d = (26 * d + b - a) % 1000007
        if i == len(s2) - 1:
            d -= 1
        if i >= l1 - 1:
            s = (s + d) % 1000007
    print s

int main (int argc, char** argv) {
    string s1, s2;
    int len1, len2;
    //scanf("%s %s %d %d", &s1, &s2, &len1, &len2);
    cin >> s1 >> s2 >> len1 >> len2;

    char ch1 = s1[0];
    char ch2 = s2[0];
    LL res = 0;
    for (int i = len1; i <= len2; ++i) {
        res += (ch2 - ch1) * pow(26, i-1);
        LL sum = 0;
        for (int j = 1; j < s2.size(); j++) {
            char temp = 0;
            if (j > s1.size()-1) {
                temp = 'a';
            } else {
                temp = s1[j];
            }
            sum += (s2[j] - temp) * pow(26, i-j-1);
        }
        res += sum;
    }
    res--;
    cout << res%1000007 << endl;

    return 0;
}

#include<iostream>
#include<string>
using namespace std;
void add_(string& s,int len){//模拟字符串s加一
    //不用考虑溢出因为函数调用前限制了条件
    if(len <= 0){
        return ;
    }
    if( s[len - 1] == 'z'){
        s[len - 1] = 'a';
        add_(s,len - 1);
    }else{
        s[len - 1] = s[len - 1] + 1;
    }
}
int get_sum_len(string& s1, string& s2, int len){
    //计算 s1 和 s2之间（包含s1,s2）有多少个长度为len的序列
    if( len <= 0 || s1 >= s2){
        return 0;
    }
    int count = 1;
    while(s1 < s2){
        add_(s1, len);
		count++;
    }
    return count;
}
int main(){
    string s1,s2;
    int len1,len2;
    while(cin>>s1 >> s2 >> len1 >> len2){
        int sum = 0;
        for(int i = len1; i <= len2; i++){
            //每次循环计算出有多少个长度为i，在s1和s2之间的序列
            string tem1 = s1;
            string tem2 = s2;
            if(i > tem1.size()){//sum 不变 补a
                while( i > tem1.size() ){
                    tem1 += 'a';
                }
            }else{//sum减一
                sum -= 1;
            }
            if( i >= tem2.size() ){//sum - 1 补a
                while( i > tem2.size() ){
                    tem2 += 'a';
                }
                sum -= 1;
            }
            tem1 = tem1.substr(0,i);//截断
            tem2 = tem2.substr(0,i);//截断
            sum += get_sum_len(tem1, tem2, i);
            sum %= 1000007; 
        }
        cout <<sum <<endl;
    }
 return 0;
}

""" 思路：遍历 m-n 位字符串，符合要求的个数是两个字符串的差值
比如 ab ce 1-2
先求 1 位字符串，符合要求的个数
n = 'c' - 'a'  // python 用 ord() 获取 ascii 码

求 2 位字符串，符合要求的个数
n = 'ce' - 'ab' = 55 // 字母是 26 个数，不能按照 10 进制计算，而是 26 进制

这样计算的结果包括了 'ce' 最后结果得减 1  """ 
while True:
    try:
        s = raw_input()
        if s == None:
            break
        sa, sb, m, n = s.split()
        la = len(sa)
        lb = len(sb)
        sum = 0
        for i in range(int(m),int(n)+1):
            if i>la or i>lb:
                break
            t = 0
            n = 0
            while t<i:
                tmp = ord(sb[t])-ord(sa[t])
                n = (n*26 + tmp)%1000007
                t = t + 1
            sum = (sum + n)%1000007
        print sum - 1
    except: 
 break 

#include<iostream>
#include<string>
#include<vector>
#include<math.h>
using namespace std;

int main(){
    //根据题中给出的例子，这个字符串只包含小写字母，不然答案就不应该是56了
    string s1,s2;
    int len1,len2;
    while(cin>>s1>>s2>>len1>>len2){
        //只包含小写字母的字符串可以看成26进制的数制
        //将s1和s2补长到len2长度
        s1.append(len2-s1.size(),'a');
        s2.append(len2-s2.size(),(char)('z'+1));
        vector<int> array;
        for(int i=0;i<len2;i++){
            array.push_back(s2[i]-s1[i]);
        }
        int result = 0;
        for(int i=len1;i<=len2;i++){
            for(int k=0;k<i;k++){
                result += array[k]*pow(26,i-1-k);
            }
        }
        //所有字符串最后都不包含是s2自身，所以最后要减1；
        cout<<result-1<<endl;
    }
    return 0;
}

import java.util.*;
public class Main{
    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            long result = 0;
            String begin = sc.next();
            String end = sc.next();
            int len1 = sc.nextInt();
            int len2 = sc.nextInt();
            int maxlen = begin.length()>end.length()?begin.length():end.length();
            int minlen = begin.length()<end.length()?begin.length():end.length();
            for(int i=0;i<maxlen;i++){
                int distance;
            	if(i<minlen){
                	distance = end.charAt(i)-begin.charAt(i);
                	
                }else{
                    if(begin.length()>end.length())
                        distance = 'a' - begin.charAt(i)-1;
                    else
                        distance = end.charAt(i)-'a'+1;
                }
                long now=0;
                for(int j=len1;j<=len2;j++){
                    if(j-i-1>=0){
                        now=now+(long)Math.pow(26,j-i-1);
                    }
                }
                now = (now*distance)%1000007;
                result+=now;
            }
            System.out.println(result-1);
        }
    }
}

//想明白了思路就很简单，代码也很少。
//求解大于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,len - 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;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int a = 1000007;
const int maxn = 100+5;
int len1, len2, ls1, ls2;
char s1[maxn];
char s2[maxn];
long long ans_arr[100000+1];

int main(){
    long long ans = 0;
    while(scanf("%s%s%d%d", s1, s2, &len1, &len2) == 4){
        ls1 = strlen(s1); ls2 = strlen(s2);
        int k = 0;
        memset(ans_arr, 0, sizeof(ans_arr));
        ans = 0;
        while(s1[k] == s2[k]) k++;
        ans_arr[k+1] = s2[k] - s1[k];
        for(int i=k+2;i<=len2;i++){
            int stuff = 0;
            if(i <= ls1) stuff += 'z' - s1[i-1];
            if(i < ls2) stuff -= 'z' - s2[i-1];
            if(i == ls2) stuff -= 'z' - s2[i-1] + 1;
            ans_arr[i] = ans_arr[i-1]*26 % a + stuff;
        }
        for(int i=len1;i<=len2;i++) ans += ans_arr[i];
        cout<<ans<<endl;
    }
    return 0;
}

#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;
}

/**
字符串计数:求字典序在s1和s2之间的，长度在len1到len2的字符串的个数，结果mod 1000007。
参照了前几位大牛的代码，并做了稍微的改动。
先举个10进制的例子：
138-->652 的三位数有几个？ (6-1)*10^2 + (5-3)*10^1 + (2-8)*10^0 = 5*100+2*10+(-6)*1 = 514 == 652-138
可以看出，514中不包括138,但是包括514,所以大于138小于652的数就是再去掉一个数(652)==652-1=651
如果是四位数呢？那就是1380-->6520之间的数，6520-1380=5140(这里只可以看出，不包含6520,因为字典序中，
652<6520, 但是包括1380,因为字典序中1380>138, 所以，这个5140就四位数的个数。

同样可以分析，18-->656 中1到四位数，这里会发现，
	1位数的个数n1就是6-1=5(不包含1，而包含6）
	2位数的个数就是n2=n1*10+(5-8) (不包含18,但包含65)
	3位数的个数就是n3=n2*10+(6-0) (这里18不够三位数，补上0，变成180, 这里不包含180而包含656,刚才应该不包含656而包含180)
	4位数的个数就是n4=n3*10+(0-0) (这里两个数都不足四位数，补0为1800->6560, 不包含1800,而包含6560,实际上应该包含1800而不包含6560,但是对计数没有影响)
同样，字母a-z就是26进制,也这么算。

综上：只有s1的长度和s2的长度相等时，才会多加一个s2,否则不会多加，也就不用减1。
以下测试用例: 
a ac 1 2 -->aa, ab -->2
aa ac 2 3 --> ab, aa(a-z), ab(a-z)-->53
牛客网的测试用例不够充分，所以很多情况测不出来。
*/
#include<iostream>
#include<string>
#include<vector>
#include<math.h>
using namespace std;
#define M 1000007
int main() {
#ifdef LOCAL_DEBUG
	freopen("input.txt", "r", stdin);
#endif
	//根据题中给出的例子，这个字符串只包含小写字母，不然答案就不应该是56了
	string s1, s2;
	int len1, len2;
	while (cin >> s1 >> s2 >> len1 >> len2) {
		//只包含小写字母的字符串可以看成26进制的数制
		//将s1和s2补长到len2长度
		int tlen1 = s1.size();
		int tlen2 = s2.size();
		s1.append(len2 - s1.size(), 'a');
		s2.append(len2 - s2.size(), (char)('a'));
		vector<int> array;
		for (int i = 0; i < len2; i++) {
			array.push_back(s2[i] - s1[i]);
		}
		int result = 0;
		for (int j = 0; j < len1 - 1; j++) {
			result = (26 * result + array[j])%M;
		}
		int sum = 0;
		for (int i = len1 - 1; i < len2; i++) {
			result = ((26 * result) % M + array[i]) % M;
			sum = (sum + result) % M;
		}
		if (tlen1 == tlen2)
			sum = (sum - 1 + M) % M;
		cout << sum << endl;
	}
	return 0;
}