读书人

请帮忙优化解决办法

发布时间: 2012-10-12 10:17:04 作者: rapoo

请帮忙优化
我这道题改了又改,找了好多种方法来来做,结果都超时,时间限制在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;} 

读书人网 >C++

热点推荐