【信息学奥赛】1400：统计单词数

统计单词数也需要分割单词，如果使用字符数组来做的话，其实和1144：单词翻转类似，但是我一直只能通过四个样例，估计边界处理条件还是有点问题。

不过经过打印字符串长度之后发现了之前遇到的一个问题，即fgets在输入的时候会将结束的换行也算进长度。

下述是前面写出来的通过的1144：单词翻转对应的代码，一开始我一直以为最后一个单词的处理是end=len-1，但是一直出错，我还在想为什么会是len-2呢？其实是fgets读取的字符数组的最后一位是换行。如果不太理解，可以通过将空白符转换为显示化内容显示出来，比如,等。

1144：单词翻转的正确做法：

#include <iostream>
#include <cstring>
using namespace std;char s[505];int main() {fgets(s, 505, stdin);int len = strlen(s);int start = 0, end = 0;for (int i = 0; i < len; i++) {if (s[i] == ' ') {end = i - 1;for (int j = end; j >= start; j--) {cout << s[j];}if (i != len - 1) { // 如果不是最后一个单词cout << " ";}start = i + 1;}}// 处理最后一个单词end = len - 2;for (int j = end; j >= start; j--) {cout << s[j];}cout << endl; // 输出一个换行符，保证输出格式正确return 0;
}

发现上述问题后，再进行编写该题，但发现还是有点问题，我想的边界条件是最后一个单词是所述单词，其他边界条件还没想到。

由于是尝试使用字符数组写出来的，所以代码有点冗余。

1400：统计单词数的半残次品做法：

#include<iostream>
#include<cstring>
using namespace std;void transform(char *s);
void ismatch(char *p,char *s);char p[30];
char s[500];int ind=0;  //下标
int num=0;  //个数int main()
{scanf("%s",p);//cout<<strlen(p)<<endl;getchar(); //去掉空格fgets(s,500,stdin);s[strlen(s)-1]=' '; //将最后的空白符替换成空格//cout<<strlen(s)<<endl;transform(p);transform(s);//   cout<<p<<endl<<s<<endl;ismatch(p,s);if(num==0)cout<<"-1"<<endl;elsecout<<num<<" "<<ind<<endl;return 0;
}//转换成小写
void transform(char *s)
{for(int i=0;i<strlen(s);i++){if(s[i]>='A'&&s[i]<='Z')s[i]+=32;}
}//s已经处理过
void ismatch(char *p,char *s)
{int len1=strlen(p),len2=strlen(s),start=0;//cout<<strlen(p)<<endl;//cout<<strlen(s)<<endl;bool flag=true,flagi=false;for(int i=0;i<len2;i++){if(s[i]==' '){if(len1==(i-start)) //长度相等{flag=true;for(int j=0,k=start;j<len1;j++,k++){if(p[j]!=s[k]){flag=false;break;}}if(flag){num++;if(!flagi){ind=start;flagi=true;}}}start=i+1;}}
}

后来反复看才知道，是题目没说清楚，文章长度范围是1<=len<=1000000，所以将上述s数组开大了一点，但是后面五个案例超时了。

1400：统计单词数的半残次品做法更正后的超时做法1：

#include<iostream>
#include<cstring>
using namespace std;void transform(char *s);
void ismatch(char *p,char *s);char p[30];
char s[1000010];int ind=0;  //下标
int num=0;  //个数int main()
{scanf("%s",p);//cout<<strlen(p)<<endl;getchar(); //去掉空格fgets(s,1000010,stdin);s[strlen(s)-1]=' '; //将最后的空白符替换成空格//cout<<strlen(s)<<endl;transform(p);transform(s);//   cout<<p<<endl<<s<<endl;ismatch(p,s);if(num==0)cout<<"-1"<<endl;elsecout<<num<<" "<<ind<<endl;return 0;
}//转换成小写
void transform(char *s)
{for(int i=0;i<strlen(s);i++){if(s[i]>='A'&&s[i]<='Z')s[i]+=32;}
}//s已经处理过
void ismatch(char *p,char *s)
{int len1=strlen(p),len2=strlen(s),start=0;//cout<<strlen(p)<<endl;//cout<<strlen(s)<<endl;bool flag=true,flagi=false;for(int i=0;i<len2;i++){if(s[i]==' '){if(len1==(i-start)) //长度相等{flag=true;for(int j=0,k=start;j<len1;j++,k++){if(p[j]!=s[k]){flag=false;break;}}if(flag){num++;if(!flagi){ind=start;flagi=true;}}}start=i+1;}}
}

既然显示超时，那么算法思路应该是没问题的，主要是需要优化算法的时间复杂度和空间复杂度啦。

将上述更改为朴素匹配法，发现仍然超时，这是因为复杂度为O(len1*len2)，其中len1是单词长度，len2是文章长度，这样很容易超时。

1400：统计单词数的半残次品做法更正后的超时做法2：

#include<iostream>
#include<cstring>
using namespace std;void transform(char *s);
void ismatch(char *p,char *s);char p[30];
char s[1000010];int ind=0;  //下标
int num=0;  //个数int main()
{scanf("%s",p);//cout<<strlen(p)<<endl;getchar(); //去掉空格fgets(s,1000010,stdin);s[strlen(s)-1]=' '; //将最后的空白符替换成空格//cout<<strlen(s)<<endl;transform(p);transform(s);//   cout<<p<<endl<<s<<endl;ismatch(p,s);if(num==0)cout<<"-1"<<endl;elsecout<<num<<" "<<ind<<endl;return 0;
}//转换成小写
void transform(char *s)
{for(int i=0;i<strlen(s);i++){if(s[i]>='A'&&s[i]<='Z')s[i]+=32;}
}//s已经处理过
void ismatch(char *p,char *s)
{int len1=strlen(p),len2=strlen(s),start=0;//cout<<p<<endl;//cout<<strlen(p)<<endl;//cout<<s<<endl;//cout<<strlen(s)<<endl;for(int i=0;i<len2;i++) //i表示起始位置{int j; //在for外面int就不要再在for里面int了for(j=0;j<len1;j++) //j表示待匹配位置 {//cout<<"j:"<<j<<endl;//cout<<"s[i+j]:"<<s[i+j]<<endl;//cout<<"p[j]:"<<p[j]<<endl;if(s[i+j]!=p[j])break;if(i>0&&s[i-1]!=' ')break;}//cout<<"j:"<<j<<endl;if(j==len1&&s[i+j]==' '){num++;if(num==1)ind=i;}}
}

如果不是按照字符输入，而是按照单词输入，再判断单词和单词是否匹配，那么将会大大降低复杂度，一个单词则使用字符串存储，一篇文章则使用字符串数组存储。

字符串，最好使用string来处理，其中自带很多函数，下面是通过的字符串匹配的暴力算法，即朴素算法。

1400：统计单词数的正确做法：

#include<bits/stdc++.h>
using namespace std;string word,sen; //word表示单词 sen表示句子
int ans; //表示个数
int ind; //表示第一次初始的位置int main()
{getline(cin,word); //读取单词getline(cin,sen); //读取句子int len1=word.size();int len2=sen.size();for(int i=0;i<len2;i++) //遍历句子 表示起始位置{int j;for(j=0;j<len1;j++) //遍历单词 表示当前单词位置{if(tolower(sen[i+j])!=tolower(word[j])) //对应字符不相等break;if(i>0&&sen[i-1]!=' ') //当前不为第一个单词且当前前一个不为空格 则表示不为独立单词break;}if(j==len1&&sen[i+j]==' '||i+j==len2) //如果为单词尾且后面有空格 或者为文章尾部{ans++; //满足的个数if(ans==1) //第一次出现ind=i; //记录下标}}if(ans)cout<<ans<<" "<<ind<<endl;elsecout<<-1<<endl;return 0;
}

注意：使用字符数组需谨慎！尝试尝试字符串！或者字符串数组！