请帮忙优化解决办法
请帮忙优化
我这道题改了又改,找了好多种方法来来做,结果都超时,时间限制在1秒内,
其中单词的长度最大为10,单词数量最大为1千万。我的程序如下,请帮忙指出
哪里可以优化!
还有一点,要匹配时,不区分大小写,但要完全匹配,单词只含有字母!
能帮忙优化者,给分!等你们的回复哦~
#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
int main()
{
string word;
string str;
int index = 0;
int trackIndex = 0;
int count = 0,
i = 0;
bool bFirst = true;
for (int sample = 1; sample <= 2; sample++)
{
cout << "输入样例" << sample << ":" << endl;
cin >> word;
for (i = 0; i < word.size(); i++)
{
word[i] = tolower(word[i]);
}
cin.get();//吸收回车符
char ch = '0';
int len1,
len2 = word.size();
while (ch != '\n')
{
cin >> str;
ch = cin.get();
len1 = str.size();
if (len1 == len2)
{
for (i = 0; i < len1; i++)
{
if (str[i] >= 'A' && str[i] <= 'Z')
{
if ((str[i] + 32) != word[i])
break;
}
else
{
if (str[i] != word[i])
break;
}
}
if (i == len1)//匹配成功
{
count ++;
if (bFirst)
{
index = trackIndex;
bFirst = false;
}
}
}
if (bFirst)//如果一直没有匹配到这个单词,那么再找下一个单词的起始位置
trackIndex += str.size() + 1;
}
cout << "输出样例" << sample << ":" << endl;
if (count != 0)
{
cout << count << " " << index << endl;
}
else
{
cout << -1 << endl;
}
count = 0;
bFirst = true;
trackIndex = 0;
}
return 0;
}
/**************************************************************
Problem: 1103
User: 1006440533
Language: C++
Result: Time Limit Exceed
****************************************************************/
------解决方案--------------------
1,不要使用c++的cin输入大数据
2,不要用STL容器,复制来复制去很费时
3,一次性读入文章,再去解析
4,题目应该是输入一篇文章,只有一个测试样例,且不要输出“测试样例”等
5,可以自己生成测试数据,测试自己方法的时间。
祝:中秋节快乐
我这道题改了又改,找了好多种方法来来做,结果都超时,时间限制在1秒内,
其中单词的长度最大为10,单词数量最大为1千万。我的程序如下,请帮忙指出
哪里可以优化!
还有一点,要匹配时,不区分大小写,但要完全匹配,单词只含有字母!
能帮忙优化者,给分!等你们的回复哦~
#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
int main()
{
string word;
string str;
int index = 0;
int trackIndex = 0;
int count = 0,
i = 0;
bool bFirst = true;
for (int sample = 1; sample <= 2; sample++)
{
cout << "输入样例" << sample << ":" << endl;
cin >> word;
for (i = 0; i < word.size(); i++)
{
word[i] = tolower(word[i]);
}
cin.get();//吸收回车符
char ch = '0';
int len1,
len2 = word.size();
while (ch != '\n')
{
cin >> str;
ch = cin.get();
len1 = str.size();
if (len1 == len2)
{
for (i = 0; i < len1; i++)
{
if (str[i] >= 'A' && str[i] <= 'Z')
{
if ((str[i] + 32) != word[i])
break;
}
else
{
if (str[i] != word[i])
break;
}
}
if (i == len1)//匹配成功
{
count ++;
if (bFirst)
{
index = trackIndex;
bFirst = false;
}
}
}
if (bFirst)//如果一直没有匹配到这个单词,那么再找下一个单词的起始位置
trackIndex += str.size() + 1;
}
cout << "输出样例" << sample << ":" << endl;
if (count != 0)
{
cout << count << " " << index << endl;
}
else
{
cout << -1 << endl;
}
count = 0;
bFirst = true;
trackIndex = 0;
}
return 0;
}
/**************************************************************
Problem: 1103
User: 1006440533
Language: C++
Result: Time Limit Exceed
****************************************************************/
------解决方案--------------------
1,不要使用c++的cin输入大数据
2,不要用STL容器,复制来复制去很费时
3,一次性读入文章,再去解析
4,题目应该是输入一篇文章,只有一个测试样例,且不要输出“测试样例”等
5,可以自己生成测试数据,测试自己方法的时间。
祝:中秋节快乐
- C/C++ code
#include <iostream> #include <string> #include <cstdio> #include <cstdlib> #include <ctime> using namespace std; //生成测试数据 void createData() { freopen("in.txt", "w", stdout); //输出重定向 int i=2; while(i--) { for( int i=0; i<5; i++) cout << (char)(rand()%26 + 'A'); //输出一个单词 cout << endl; for( int i=0; i<1000000; i++) { if( i!=0&&(i++%6==0)) cout << " "; cout << (char)(rand()%26 + 'A'); } cout << endl; } fclose(stdout); } void count1() { //string word; //string str; //freopen("in.txt", "r", stdin); int index = 0; int trackIndex = 0; int count = 0, i = 0; bool bFirst = true; for (int sample = 1; sample <= 2; sample++) { //cout << "输入样例" << sample << ":" << endl; char word[50]; scanf("%s", word); //string word = p; //cin >> word; int len2 = strlen(word); for (i = 0; i < len2; i++) { word[i] = tolower(word[i]); } char ch = '0'; int len1; while (ch != '\n') { char str[50]; scanf("%s", str); ch = getchar(); //string str = p; //string str; //cin >> str; len1 = strlen(str); if (len1==len2) { for (i = 0; i < len1; i++) { if ( str[i] >= 'A' ) { if ((str[i] + 32) != word[i]) break; } else { if (str[i] != word[i]) break; } } if (i == len1)//匹配成功 { count ++; if (bFirst) { index = trackIndex; bFirst = false; } } } if (bFirst)//如果一直没有匹配到这个单词,那么再找下一个单词的起始位置 trackIndex += len1 + 1; } //cout << "输出样例" << sample << ":" << endl; if (count != 0) { cout << count << " " << index << endl; } else { cout << -1 << endl; } count = 0; bFirst = true; trackIndex = 0; } } void Count() { //freopen("in.txt", "r", stdin); char word[12]; char *str = new char[1000002]; //在堆上申请空间 gets(word); //读入单词 char *p = word; while( *p ){ if( *p < 'a') *p += ('a' - 'A'); //改成小写 p++; } gets(str); //读入文章 char *q = str; p = word; bool find = false; //标记是否找到单词,初始未找到 int count =0; //单词出现个数 int start =0; //第一次出现位置 while( *q ) //开始解析文章 { int dis = *p-*q; //计算距离 if( dis ==0 || dis == ('a' - 'A') ) //匹配一个单词 { p++; q++; } else //出现未匹配时 { p=word; while(*q&&*q!=' ') q++; //找文章的下一个空格 while(*q==' ') q++; //找下一个单词的首字母,单词之间可能有很多空格 continue; } if( (*p==0) && (*q==0 ||*q ==' ') ) //完全匹配上,即单词结束,文章结束或者空格 { if( !find ) //第一次找到 { start = (q-str)-(p-word); //文章距离减去单词长度 find = true; } count++; p=word; //重新开始 } } if( !find ) cout << -1 <<endl; else cout << count << " " <<start<<endl; delete [] str; } int main() { //clock_t begin = clock(); //createData(); //生成单词,放入in.txt中 Count(); //cout << "Time used:" << clock()-begin<< " ms" <<endl; //计算时间 return 0; }