题目：

给出一个长度不超过200，而且全部小写英文字母组成的字符串（该字符串必须每行20个字母的方式输入）。要求将此字符串分成k份(1<k<=40)，输出最大的包含单词个数。限制条件如下：

1.每份中包含的单词可以部分重叠。

2.当选用一个单词后，其第一个字母不能再用。例如字母串this中可包含this和is，选用this之后就不能包含th，因为t开头的单词已经包含在内了。

3.单词由一个不超过6个单词的字典给出。

输入第一行为一个正整数n(0<n<=5)，表示测试数据组数。每组的第一行有两个正整数p、k。p表示子串的行数，k表示分成k个部分。再接下来有一行有一个正整数s，表示词典中单词个数(1<s<=6)。接下来的s行为词典内容，每行均有一个单词。输出n行，每行一个整数，分别对应每组测试数据的相应结果。

思路：

（说明：题中“给出一个长度不超过200，...（该字符串必须每行20个字母的方式输入）”听起来有些莫名其妙，因此不考虑这个，直接输入一行待匹配的字符串。然后关于测试数据，我也默认只有一组测试数据，如果需要按照题目输入几组测试数据的话，写一个while循环一组一组的测试即可。）

学习了一阵子动态规划，条件反射先定义一个二维数组dp[][]，本题dp[i][j]的含义为将输入字符串的前 i+1个字符组成的子字符串划分为 j 份后最大包含单词的个数。动态转移方程为：dp[i][j] = dp[m][j-1] + ([m+1,i] 区间中包含的单词个数)。

[m+1,i] 区间中包含的单词个数可以这样求：先将该部分字符串提取出来赋给substr变量，再将substr传入match_and_count函数，进行统计。而match_and_count函数的思路可以参考我的上一篇博客：c++ 求字符串中最大的包含单词个数。

另外将区间[0,i]的子字符串分为1份（不划分）时的dp[i][0]是可以提前用match_and_count函数求得的。

如果理解不了动态转移方程：dp[i][j] = dp[m][j-1] + ([m+1,i] 区间中包含的单词个数) ，可以看一下我的这一篇博客：程序基本算法习题解析 动态规划-乘积最大：设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积最大。

最后就是需要注意遍历时各层循环变量的取值范围。

代码如下：

// Chapter14_6.cpp : Defines the entry point for the application.
// 统计单词个数
// 给出一个长度不超过200，而且全部小写英文字母组成的字符串（该字符串必须每行20个字母的方式输入）。
// 要求将此字符串分成k份(1<k<=40)，输出最大的包含单词个数。限制条件如下：
// 1.每份中包含的单词可以部分重叠。
// 2.当选用一个单词后，其第一个字母不能再用。例如字母串this中可包含this和is，选用this之后就不能
// 包含th，因为t开头的单词已经包含在内了。
// 3.单词由一个不超过6个单词的字典给出。
// 输入第一行为一个正整数n(0<n<=5)，表示测试数据组数。
// 每组的第一行有两个正整数p、k。p表示子串的行数，k表示分成k个部分。
// 再接下来有一行有一个正整数s，表示词典中单词个数(1<s<=6)。
// 接下来的s行为词典内容，每行均有一个单词。
// 输出n行，每行一个整数，分别对应每组测试数据的相应结果。

#include "stdafx.h"
#include<iostream>
#include<string>
using namespace std;

const int max_dic = 6; //定义字典中所能存放的单词个数
const int maxN = 200; //字符串最大的长度
const int maxK = 40; //划分的最大份数
string str; //原字符串（输入的需要匹配的字符串）
int p; //字典中单词的个数
int k; //要划分的份数
int maxlength; //字典中最长单词的长度
string dic[max_dic]; //字典

//声明函数
int max_length(string *str,int n); //求字典中最长单词的长度函数
int match_and_count(string &substr); //求字典中最长单词的长度函数

int main()
{
	//dp[i][j]表示将输字符串的前i+1个字符组成的子字符串划分为j份后最大包含单词的个数
	int dp[maxN+1][maxK+1]; 
	memset(dp,0,sizeof(dp));
	int i,j; //循环变量
	int count = 0; //计数变量
	//输入
	cout << "输入需要匹配的字符串:" << endl;
	cin >> str;
	cout << "输入需要划分的份数:";
	cin >> k;
	cout << "输入字典中的单词个数:";
	cin >> p;
	cout << "输入字典中的单词:" << endl;
	for(i=0;i<p;i++)
		cin >> dic[i];
	//输入的字符串的长度
	int stringLength = str.length();
	//求字典中最长单词的长度
	maxlength = max_length(dic,p);
	//将区间[0,i]的子字符串分为1份（不划分）时的dp[i][0]
	//求子字符串
	string substr = ""; //substr为区间[m,i]之间的子字符串
	for(i=0;i<stringLength;i++)
	{
		substr = substr + str[i]; 
		dp[i][1] = match_and_count(substr);
	}
	//动态规划思想求dp[i][j]
	//i的取值范围是[0,stringLength)
	for(i=0;i<stringLength;i++)
	{
		//j的取值范围是[1,k]，但是j=1时的dp[i][j]值之前单独求过了，因此这里j从2开始
		for(j=2;j<=k;j++)
		{
			//要保证字符串长度大于划分的份数
			if(i>=j)
			{
				count = 0; //对于每个dp[i][j]，count需要初始化为0
				for(int m=0;m<i;m++)
				{
					//求子字符串
					substr = ""; //substr为区间[m+1,i]之间的子字符串
					for(int l=m+1;l<=i;l++)
						substr = substr + str[l]; 
					//求substr中最大包含的单词数
					count = match_and_count(substr);
					//动态转移方程
					dp[i][j] = dp[m][j-1] + count;
				}
			}
		}
	}
	cout << "最大的包含单词个数为：" << dp[stringLength-1][k] << endl;
	system("pause");
	return 0;
}

//求字典中最长单词的长度函数
int max_length(string *str,int n)
{
	int max = str[0].length();
	for(int i=1;i<n;i++)
	{
		if(str[i].length() > max)
			max = str[i].length();
	}
	return max;
}

//匹配和计数函数
int match_and_count(string &substr)
{
	int subcount = 0; //函数中的计数变量
	int i;
	//left:切片的起始位置，right:切片的终止位置
	int left = 0,right = 0;
	//切片的起始位置移动到原字符串的末尾为止
	while(left < substr.length())
	{
		//left加1和right加1的标志变量，flag=0表示未找到匹配，right加1；flag=1表示找到匹配，left加1
		int flag = 0; 
		//遍历不同长度的子字符串
		for(right=left;right<= left+maxlength;right++)
		{
			//求子字符串
			string temp = "";
			for(i=left;i<=right;i++)
				temp = temp + substr[i]; 
			//与字典中的单词进行比对
			for(i=0;i<p;i++)
			{
				//若匹配到一个单词
				if(temp == dic[i])
				{
					subcount++; //计数变量加1
					flag = 1; //flag置1（目的是退出外for循环）
					break;
				}
			}
			if(flag == 1)
				break;
		}
		//从下个字符开始进行匹配
		left++;
	}
	return subcount;
}


运行结果如下：

python在单词表中查找包含所有元音字母aeiou的单词并打印
python单词表中查找所有的元音字母aeiou:

方法一：
 def claen(word):
            return word.strip().lower()
         
 def lookUpWord(word):
       newword = ""
       for char in word:
           if char in 'aeiou':
               newword += char
           return newword
           
if __name__ == '__main__':
    try:
       with open(r'dictionary.txt') as f:
           for word in f:
               word = claen(word)
               wordstr = lookUpWord(word)
               if wordstr == 'aeiou':
                  print(word)
     finally:
        f.close()

方法二：
def claen(word):
            return word.strip().lower()
        
 def lookupword(word):
     vowelsInWord = ""
     for char in word:
         if char in 'aeiou':
            vowelsInWord +=char
         return vowelsInWord
            
if __name__ == '__main__':        
	 try:
         with open(r'dictionary.txt') as f:
              for word in f:
                  word = claen(word)
                  if len(word) < 5:
                      continue
                  vowelStr = lookupword(word)
                  if vowelStr == 'aeiou':
                     print(word)
    finally:
       f.close()

程序运行截图：

2015届蓝桥杯B组1：

输入一个字符串，求它包含多少个单词。单词间以一个或者多个空格分开。

第一个单词前，最后一个单词后也可能有0到多个空格。

比如：" abc    xyz" 包含两个单词，"ab   c   xyz    "  包含3个单词。

如下的程序解决了这个问题，请填写划线部分缺失的代码。

注意：只填写划线部分的代码，不要填写任何多余的内容。比如已经存在的小括号，注释或说明文字等。



int get_word_num(char* buf)

{

    int n = 0;   

    int tag = 1;

    char* p = buf;

    

    for(;*p!=0 && *p!=13 && *p!=10;p++){

        if(*p==' ' && tag==0) tag=1;

        if( *p!=' ' && tag==1 ) { n++; tag=0; }   //填空

    }

    

    return n;

}

int main()

{

    char buf[1000];

    fgets(buf,1000,stdin);

    

    printf("%d\n", get_word_num(buf));

    return 0;

}

当前一位是空格，但后一位不是空格时就代表一个单词出现，n++。

 

 

深信服2018秋招笔试题：

输入一个字符串，帮忙统计字符串里面的每个单词出现的次数，以及非法单词的次数。非法单词的定义为：包含数字（0-9）的单词

输入一个字符串，长度小于1000，输入的字符仅包含（0-9，a-z,A-Z, . , : ! ）及空格。

输出按单词的字母进行排序，每行为 ：

单词    单词出现次数

最后一行输出非法单词个数

实例1：

输入：

wow! Is wonderful!

输出：

Is 1

wonderful 1

wow 1

0

实例2：

输入：

abc bcd2 fe fe a3xd

输出：

abc 1

fe 2

2

代码如下：

#include<iostream>
#include<map>
#include<string>
#include<vector>

using namespace std;
int main()
{
	string str;
	map<string, int>temp;
	getline(cin, str);
	int plow = 0, phigh = 0;
	string s = "";
	while (phigh < str.length())
	{
		if (str[phigh] == ' ')
		{
			phigh++;
			plow = phigh;
			temp[s]++;
			s = "";
			continue;

		}
		else
		{
			s = s + str[phigh];
			if (phigh == str.length() - 1) temp[s]++;
			phigh++;
		}

	}
	vector<string>res;
	auto j = temp.begin();
	while(j != temp.end())
	{
		string tmp = j->first;
		int len = tmp.size();
		for (int i = 0; i < len; i++)
		{
			if (!(tmp[i] >= 65 && tmp[i] <= 90 || tmp[i] >= 97 && tmp[i] <= 122))
			{
				if (tmp[i] >= 48 && tmp[i] <= 57)
				{
					res.push_back(tmp);
					j = temp.erase(j);
					j--;
					break;
				}

			}
			else if (tmp[len-1] == 44 || tmp[len-1] == 46 || tmp[len-1] == 58 || tmp[len-1] == 33) {
				string new_tmp(tmp.begin(), tmp.end() - 1);
				int b = j->second;
				temp.insert(make_pair(new_tmp, b));
				j = temp.erase(j);
				j--;
				break;
			}
		}
		j++;
	}
	for (auto s = temp.begin(); s != temp.end(); s++)
	{
		cout << s->first << " " << s->second << endl;
	}
	cout << res.size() << endl;

	system("pause");
    return 0;
}


主要是对问题的仔细分析！然后就是注意细节，特别是迭代器的失效问题，位置变换等问题！