微软必应·英豪会第三届在线编程大赛：几个bing? 题目解析

微软必应·英雄会第三届在线编程大赛：几个bing? 题目解析
解题思路在博客里写了http://blog.csdn.net/rzleilei/article/details/17796523
代码如下。

另外本人欢迎提供或交流类似的编程题目。

题目详情:

    本届大赛由微软必应词典冠名，必应词典(http://cn.bing.com/dict/?form=BDVSP4&mkt=zh-CN&setlang=ZH)是微软推出的新一代英语学习引擎，里面收录了很多我们常见的单词。但现实生活中，我们也经常能看到一些毫无规则的字符串，导致词典无法正常收录，不过，我们是否可以从无规则的字符串中提取出正规的单词呢？

   例如有一个字符串"iinbinbing"，截取不同位置的字符‘b’、‘i’、‘n’、‘g’组合成单词"bing"。若从1开始计数的话，则‘b’ ‘i’ ‘n’ ‘g’这4个字母出现的位置分别为(4,5,6,10) (4,5,9,10),(4,8,9,10)和(7,8,9,10)，故总共可以组合成4个单词”bing“。

  咱们的问题是：现给定任意字符串，只包含小写‘b’ ‘i’ ‘n’ ‘g’这4种字母，请问一共能组合成多少个单词bing?

  字符串长度不超过10000，由于结果可能比较大，请输出对10^9 + 7取余数之后的结果。 

public class Test4 {
	static char[] ch;
	static int index=0;
	static int b_num=0;
	static int i_num=0;
	static int n_num=0;
	static int num=0;
	
	public static void main(String[] args) {
		
		System.out.println(getNum("iinbinbinginng"));
	}
	
	public static int getNum(String str){
		ch=str.toCharArray();
		for (int i = 0; i < ch.length; i++) {
			switch (ch[i]) {
			case 'b':
				b_num++;
				break;
			case 'i':
				i_num+=b_num;
				break;
			case 'n':
				n_num+=i_num;
				break;
			case 'g':
				num+=n_num;
				break;
			default:
				break;
			}
		}
		return num%(10^9+7);
	}
}

------解决方案--------------------

惭愧，想法跟你类似。只是写得麻烦了不少。你的好简洁的说.:

int howmany (const char* s)
{    
    unsigned int len = 0;
    const char* e = s;
    const char* key = "bing";
    const char* ke = key;
    unsigned int keyLen = 0;
    long long num = 0;
    long long* bing = 0;
    int idx[256] = {0};
    unsigned int i = 0;

    if(s == 0 
------解决方案--------------------
 *s == 0) return 0;
    
    while(*ke++ != 0);
    while(*++e != 0);
    keyLen = ke - key - 1;

    bing = (long long*)malloc(sizeof(long long) * keyLen);
    for(i = 0; i < keyLen; ++i)
    {
        idx[key[i]] = i + 1;
        bing[i] = 0;
    }

    for (--e; e >= s; --e)
    {
        int n = idx[*(unsigned char*)e];

        if(!n)
            continue;
        
        if(n == keyLen)
        {
            bing[n - 1]++;
        }
        else
        {
            if(bing[n] > 0)
                bing[n - 1] += bing[n];
        }
    }

    num = bing[0];
    free(bing);
    return num % 1000000007;
}

------解决方案--------------------
    public static int howmany(string s)
    {
        char[] str = s.ToCharArray();
        int b_num = 0;
        int i_num = 0;
        int n_num = 0;
        int num = 0;

        for (int i = 0; i < str.Length;i++)
        {
            switch (str[i])
            {
                case 'b':
                    b_num++;