(?!单词).
这个是为了匹配某单词,无后缀。
然后用(?:)的循环语句廓上,循环0次,就搞定了
(?:(?!单词).)*
eg:
/(http:\/\/[^'"<>(),\\s\r\n!\x80-\xff](?:(?!http:|https:).)+)/i
包名不应该用来表达模块完整的意思,包名应该仅用作与同包下的其他包做区分。
遇到适当的时候应该向范围更大的语义上取名,如已存在一个包代表 51-100 的范围,现在你想新建一个包 1-30,如果不存在 31-50,应当向上取包名成为 1-50;如果存在 31-50,应当取包名为 1-50.1-30 和 1-50.31-50 两个包。
对于题中的情况,应该去除重复的部分,仅留下关键区分的信息:
com.coalmine.management
com.coalmine.execution
如果除了子系统,还有非子系统,那就命名为:
com.coalmine.subsystem.management
com.coalmine.subsystem.execution
如果除了生产子系统,还有非生产子系统,那就命名为:
com.coalmine.subsystem.production.management
com.coalmine.subsystem.production.execution
题目:
给出一个长度不超过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;
}
运行结果如下:
(?!单词).
这个是为了匹配某单词,无后缀。
然后用(?:)的循环语句廓上,循环0次,就搞定了
(?:(?!单词).)*
eg:
/(http:\/\/[^'"<>(),\\s\r\n!\x80-\xff](?:(?!http:|https:).)+)/i
转载于:https://my.oschina.net/pureboys/blog/613417
【描述】
输入1行句子(不多于200个单词,每个单词长度不超过100),只包含字母、空格和逗号。单词由至少一个连续的字母构成,空格和逗号都是单词间的间隔。
试输出第1个最长的单词和第1个最短单词。
【输入】
一行句子。
【输出】
两行输出:
第1行,第一个最长的单词。
第2行,第一个最短的单词。
【样例输入】
I am studying Programming language C in Peking University
【样例输出】
Programming
I
这个题目思路是这样:先用gets函数输入整行字符串a,然后扫描a串分割出各个单词,依次比较新分割的单词的长度是否比已经发现的单词中最长、最短单词还要长或短,若是有需要在更新一经发现的最长、最短单词并更新最长、最短单词的长度。
这里关键是扫描、分割单词。由于空格和逗号都是单词的分隔符号,所以可以把他们两种符号一起处理。扫描分割的过程需要用标志性变量f。f=0表示当前遇到的分隔符(空格或逗号)是新单词之前的分隔符; f=1表示当前遇到的分隔符前面有一个刚刚扫描形成的单词,也就是已经扫描分割出一个单词,需要对该单词做处理(求长度newLen,用newLen和max、min比较)。注意:在处理完一个单词后需要把f重新设为0.
注意1:输入的串的开头、结尾可能有分隔符,也可能没有分隔符。所以末尾单词不一定被拿来跟max和min作比较。需要在循环后单独处理。
注意2:如果所有单词长度相同,那么第一个单词既是最长单词也是最短单词。
#include<stdio.h>
#include<string.h>
int main(void){
char a[20200],b[101],maxT[101]="",minT[101]="";
int i=0,j=0;
int max=-1,min=101,newLen;
int f=0; //f=0表示当前遇到的分隔符(空格或逗号)是新单词前的分隔符
gets(a);
while(a[i]!='\0'){ //扫描a串生成一个新的单词,然后测其长度,再与max,min对比
if(a[i]==' '||a[i]==','){
if(f==1){ //f=1表示当前遇到的分隔符前面有一个刚刚扫描形成的单词
b[j]='\0';
newLen=strlen(b);
if(newLen>max) {
max=newLen;
strcpy(maxT,b);
}
if(newLen<min){
min=newLen;
strcpy(minT,b);
}
f=0;
j=0;
}
}
else{
b[j]=a[i];
j++;
f=1; //开始或是正在构造一个单词
}
i++;
}
//处理末尾单词
b[j]='\0';
newLen=strlen(b);
if(newLen>max) {
max=newLen;
strcpy(maxT,b);
}
if(newLen<min){
min=newLen;
strcpy(minT,b);
}
printf("%s\n%s\n",maxT,minT);
return 0;
}
原作者博客
https://www.cnblogs.com/huashanqingzhu/p/5075332.html