洛谷 P1308(统计单词数)题解

不得不说软工的兼班兼助还是很 Nice 的,爆照唱歌女装伪声之余居然还能给我们答疑…

NOIP 2011 普及组第 2 题

一般的文本编辑器都有查找单词的功能,该功能可以快速定位特定单词在文章中的位置,有的还能统计出特定单词在文章中出现的次数。

现在,请你编程实现这一功能,具体要求是:给定一个单词,请你输出它在给定的文章中出现的次数和第一次出现的位置。注意:匹配单词时,不区分大小写,但要求完全匹配,即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同(参见样例 1),如果给定单词仅是文章中某一单词的一部分则不算匹配(参见样例 2)。

输入格式

共 2 行。第 1 行为一个字符串,其中只含字母,表示给定单词;第 2 行为一个字符串,其中只可能包含字母和空格,表示给定的文章。

输出格式

一行,如果在文章中找到给定单词则输出两个整数,两个整数之间用一个空格隔开,分别是单词在文章中出现的次数和第一次出现的位置(即在文章中第一次出现时,单词首字母在文章中的位置,位置从 0 开始);如果单词在文章中没有出现,则直接输出一个整数 -1。

输入输出样例

输入样例 #1:

To
to be or not to be is a question

输出样例 #1:

2 0

输入样例 #2:

to
Did the Ottoman Empire lose its power at that time

输出样例 #2:

-1

数据范围

1 ≤ 单词长度 ≤ 10,1 ≤ 文章长度 ≤ 1,000,000。

思路

单词匹配个人是这样理解的:

Step 1 进行大小写转换

用 ASCII 码好实现,做做加法就行了。

Step 2 找到一个单词

前面一个空格,后面一个空格,中间夹着的自然是单词了。但是开头第一个词例外,因为第一个词前面没有空格。

Step 3 确认这个单词和待查找的相符

逐个单词和待匹配的单词一一匹配?文章长度可达 1,000,000 字符,不可能这样做,而且情况也复杂。于是我们先简化一下,当待文章单词和待匹配的单词字符数相同再看看是不是匹配的。这样就简单了,逐个字符比对就是了。

#include <stdio.h>
#include <string.h>
int main(){
    char a[12], b[1000002];
    int s=0,flag=0,flag2,temp;
    gets(a); gets(b);
 
    for (int i = 0; i < strlen(a); i++)
    {
        if (a[i]>=65 && a[i]<=90) a[i]+=32;
    }
    for (int i = 0; i < strlen(b); i++)
    {
        if (b[i]>=65 && b[i]<=90) b[i]+=32;
    }

    for (int i = 0; i < strlen(b); i++)
    {
        temp=i+strlen(a);
        if( b[i]==a[0] && ( b[i-1]==32 || i==0 ) && b[temp]==32 )
        {
            flag=0;
            for (int j = 0; j < strlen(a); j++)
            {
                if (a[j]!=b[i+j])
                {
                    flag=1;
                    break;
                }
                
            }
            if (flag==0)
            {
                s++;
                if (s==1)
                {
                    flag2=i;
                }    
            }            
        }
    }
    if (s != 0)
    {
        printf("%d %d",s, flag2);
    }
    else
    {
        printf("-1");
    }
    return 0;
}

提交之后发现有几个测试点 TLE(超时)了,寻找兼助(隐私原因姓名略去):

午睡起来马上就开始修改了,如何才能将 A 和 a 识别成大小写关系呢,ASCII 码告诉我们,它们的值差 32,利用 abs() 函数很快就改好了。

提交,后面的几个测试点耗时都少了一半,但还是 TLE。那最后是怎样解决的呢?事实上 strlen() 被重复调用了多次浪费了极多的时间,再次修改如下:

#include <stdio.h>
#include <string.h>
#include <math.h>
char a[12], b[1000002];
int main(){
    int s=0,flag=0,flag2,temp,strlenA,strlenB;
    gets(a);
    gets(b);
    strlenA=strlen(a);
    strlenB=strlen(b);
    for (int i = 0; i < strlenB; i++)
    {
        temp=i+strlenA;
        if( (a[0]==b[i] || abs(a[0]-b[i])==32) && ( b[i-1]==32 || i==0 ) && b[temp]==32 )
        {
            flag=0;
            for (int j = 0; j < strlenA; j++)
            {
                if (a[j]!=b[i+j] && abs(a[j]-b[i+j])!=32)
                {
                    flag=1;
                    break;
                }               
            }
            if (flag==0)
            {
                s++;
                if (s==1) flag2=i;   
            }            
        }
    }
    if (s != 0) printf("%d %d",s, flag2);
    else printf("-1");
    return 0;
}

AC 了,这回减少的时间就多了。跟兼助报喜: