文章来源：http://blog.csdn.net/aa512690069/article/details/17918799
其原文是微软一个小题目：http://hero.csdn.net/Question/Details?ID=215&ExamID=210
本届大赛由微软必应词典冠名，必应词典(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取余数之后的结果。
******************************************************************************
我的思路（这个思路只是针对任何单词，前提是单词中没有重复的字母，比如说：good，o重复了则不适用，原因是加上重复字母的话得复杂不少而没有做）：按照例子 “iinbinbing“ 来说，可以画出如下4张图，来对应bing的4种情况，其纵轴是该字符出现在字符串中的索引（1开始）:
那么这个统计问题就转换成了线段从b开始连接到尾部g的线路数，且连接的点位置必须满足前一个字母位置小于后一个字母位置（顺序）。
如下图，bing的组成个数 n = b1 + b2。 n = 1 + 3 = 4;
有了这个想法，然后开始想办法统计连接到尾部的线路数加总即可.既然是统计到尾部的线路数，当然从尾部开始找。于是乎，得到如下统计图表：
有了这个想法，然后开始想办法统计连接到尾部的线路数加总即可.既然是统计到尾部的线路数，当然从尾部开始找。于是乎，得到如下统计图表：
那么，其实我们就是为了求总数，而不必要得到每一点的所有线路，所以。我们每一步执行都加总一次，即得到如下图:
那么，这个图的字母b的第一个计数器(b, 4)即为bing的组合个数。也就是连接到尾部的总个数。
结语：
这个实现的步骤复杂度为O(2N)，计算长度 + 统计，2次循环。
可以看得出这里为什么不允许重复字母，如果是重复的字母则需要建立复合计数器（即一个字母有多个计数器，分别对不同位置进行计数），但是鉴于题目没有这些要求而没有做多余的事情。
后来发现，其实这里正着循环也行，复杂度O(N)，长度不需要计算。
实现代码如下（这个是我提交给微软考试用的题目，也就不改了）：
1 #include<stdio.h> 2 #include<malloc.h> 3 int howmany (const char* s) 4 { 5 unsigned int len = 0; 6 const char* e = s; 7 const char* key = "bing"; 8 const char* ke = key; 9 unsigned int keyLen = 0; 10 long long num = 0; 11 long long* bing = 0; 12 int idx[256] = {0}; 13 unsigned int i = 0; 14 15 if(s == 0 || *s == 0) return 0; 16 17 while(*ke++ != 0); 18 while(*++e != 0); 19 keyLen = ke - key - 1; 20 21 bing = (long long*)malloc(sizeof(long long) * keyLen); 22 for(i = 0; i < keyLen; ++i) 23 { 24 idx[key[i]] = i + 1; 25 bing[i] = 0; 26 } 27 28 for (--e; e >= s; --e) 29 { 30 int n = idx[*(unsigned char*)e]; 31 32 if(!n) 33 continue; 34 35 if(n == keyLen) 36 { 37 bing[n - 1]++; 38 } 39 else 40 { 41 if(bing[n] > 0) 42 bing[n - 1] += bing[n]; 43 } 44 } 45 46 num = bing[0]; 47 free(bing); 48 return num % 1000000007; 49 }
复杂度O(N)
1 int howmany(const char* str) 2 { 3 long long counter[4] = {0}; 4 if(str == 0) return 0; 5 6 for(; *str != 0; str++) 7 { 8 switch(*str) 9 { 10 case 'b': counter[0]++; break; 11 case 'i': counter[1]+=counter[0]; break; 12 case 'n': counter[2]+=counter[1]; break; 13 case 'g': counter[3]+=counter[2]; break; 14 } 15 } 16 return counter[3] % 1000000007; 17 }
*************************************************
以上都是原作者的分析和代码。个人感觉前面的分析没讲清楚，不过最后一段代码倒是很好。我自己写，原先想的简单，直接没考虑b、i、n、g几个字母的顺序问题，直接统计个数然后相乘（我想的太简单了⊙﹏⊙b汗）。
看了作者分析，知道要考虑顺序问题，然后再看最后一段代码，想想理解了。谢谢作者。
