Skip to content

14099: 【原4099】Love and Auto Memories Doll

题目

题目描述

author: 黄俊翔 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4099 ## Description

现在是周五晚上六点,想必家住上海的同学们很想早点回家,外地的同学多半还没吃晚饭,吃了晚饭的同学也因为经历了一周的工作学习觉得很累想要赶快去睡觉,斗志涣散,不想写题。但这对于钢铁直女紫薇酱来说都不是问题,因为紫薇没有家人,又在军队中受过执行任务时可以长时间不进食不睡觉的训练,所以她现在状态绝佳,正以200+APM的速度锐意工作中。紫薇是一名打字员,她的工作就是为客户代写书信。尽管紫薇分分钟就能码完一封信,但她在不断码字的过程中,对个别的词语产生了特别的兴趣,比方说,love。于是她开始一封一封看之前码过的信,想要从里面找出某个特定的词出现了多少次,以及第一次是在哪里出现的。

但紫薇很快发现自己码过的信太长太多,靠自己找实在是太慢了。于是她找到了你,希望你能够帮帮她。同学们的水平都很高,想必扫一眼就会说“简单的KMP算法,秒了”,但这不太符合A是一道新手签到题的设定,因此在这里特别强调一下,这里的信保证只有一行字符(结尾有个回车),用空格来分割单词,除了大小写英文字母和空格之外没有别的符号;而且还要求整个单词完全相同才算匹配(但不区分大小写),前缀后缀或者在中间都是不行的。

Input Format

输入共三行。

第一行一个单词(由大小写字母组成),回车;

第二行一个整数,表示接下来的字符串由多少个单词组成,回车;

第二行一个字符串(由大小写字母和空格组成),回车。可能有多个连续的空格和行首行末空格。

Output Format

输出共一行。

若给的单词是在字符串中出现过的单词(必须是前后被开头/空格/或回车夹着的完整单词,且忽略大小写后必须全等),则输出一行两个整数。第一个整数为字符串中有几个这样的单词;第二个整数为字符串中该单词第一次出现的位置(字符串第一个字符的位置设为0),并且该数字是忽略所有空格的,也就是空格的多少不会影响这个答案。

若在字符串中没有出现过给定的单词,输出-1。

Sample Input

数据1:

Love
13
    Dear loVe    Your charms aLoNe are beAUTiFul    Can yoU be my dEar lOVE

数据2:

moe
26
Moe te i ma sen    Moe te ru yo    Moe te i ma sen  o ka shii de su    I ya moe te ru n da

数据3:

Feeling
58
Perception of the physical world does not necessarily result in a universal reaction among receivers But varies depending up on ones tendency handle the situation How the situation relates to the receivers past experience And any number of other factors Feelings are also known as a state of consciousness Such as that resulting from emotions sentiments or desires

Sample Output

数据1:

2 4

数据2:

4 0

数据3:

-1

数据解释: 数据1在忽略所有空格(包括分割单词的空格)之后,loVe的l处在字符串中4的位置,且不区分大小写的love总共出现了两次,因此答案为2, 4。 数据2再次提醒,字符串是以0作为第一个下标的。 数据3的字符串中有单词Feelings,但是因为不是Feeling,所以输出结果为-1。

Data Range

对于\(100\%\)的数据,所有单词的长度\(1 \le W \le 250\),文章的长度\(1 \le L \le 10^7\)。

但仅对于\(90\%\)的数据,单词数\(N \le 4 \times 10^4\)。

FineArtz's solution

/* Love and Auto Memories Doll */
#include <iostream>
#include <cstring>
using namespace std;

inline void lowercase(char *s, int len){
    for (int i = 0; i < len; ++i)
        if (s[i] < 'a')
            s[i] = s[i] + 'a' - 'A';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    char s[255], w[255];
    cin >> s;
    int n, lens = strlen(s);
    lowercase(s, lens);
    cin >> n;
    int ans = 0, cnt = 0;
    while (n--){
        cin >> w;
        int l = strlen(w);
        lowercase(w, l);
        if (lens != l){
            if (cnt == 0)
                ans += l;
        }
        else{
            bool flag = true;
            for (int i = 0; i < l; ++i){
                if (s[i] != w[i]){
                    flag = false;
                    break;
                }
            }
            if (flag){
                ++cnt;
            }
            else{
                if (cnt == 0)
                    ans += l;
            }
        }
    }
    if (cnt == 0)
        cout << "-1\n";
    else
        cout << cnt << ' ' << ans << '\n';
    return 0;
}