Skip to content

14107: 【原4107】Love and Auto Memories Doll II

题目

题目描述

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

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

但紫薇很快发现自己码过的信太长太多,靠自己找实在是太慢了。于是她找到了你,希望你能够帮帮她。同学们的水平都很高,想必扫一眼就会说“简单的KMP算法,秒了!”没错,这次的题目就是简单的KMP签到题,因此在这里特别强调一下,这里的信保证只有一行字符(结尾有个回车),除了大小写英文字母和空格之外没有别的符号;和上次不一样的是,这次的信没有“用空格分割单词”的概念,空格和其他字母是一样可以被匹配的(但保证要找的单词不会包含空格),只要是信中任意位置的子串都可以匹配(但不区分大小写),而且多个匹配子串之间即使有重复的部分也仍然重复计数。举个栗子,“AaAaa aAA”中,“aaa”这个单词出现了4次。再举一个栗子,如果信中没有这个空格,那么答案就是出现了6次。

Input Format

输入共两行。

第一行一个字符串A(由大小写字母组成,没有空格,单词前后也没有多余的空格),回车;

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

Output Format

输出共一行。

若字符串A在字符串B中出现了,则输出一行两个整数。第一个整数为字符串B中有几个这样的字符串A(不区分大小写,多个匹配之间可以重叠);第二个整数为在字符串B中,字符串A第一次出现的位置(字符串第一个字符的位置设为0)。本题中空格和其他的字母都是等价(占位置)的。

若在字符串中B没有出现过字符串A,输出-1。

Sample Input

数据1:

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

数据2:

aAba
aaBaabAaba Aba

数据3:

Shousa
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 9

数据2:

3 0

数据3:

-1

数据解释:

数据1的前面有四个空格,love出现两次,故答案为2 9。

数据2提醒,字符串是以0作为第一个下标的,匹配之间是可以有重复部分的,以及空格影响匹配(没有空格答案就是4 0了)。

数据3是英文wiki的内容当然不会有少佐这个词,所以请记得输出-1。

Data Range

对于\( 50\% \) 的数据,字符串A的长度\( 1 \le W \le 200 \),字符串B的长度\(1 \le L \le 10^5\)。

对于\( 100\% \) 的数据,字符串A的长度\( 1 \le W \le 10^7 \),字符串B的长度\(1 \le L \le 10^7\)。

FineArtz's solution

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

const int MAXS = 10000000;

char a[MAXS + 5], b[MAXS + 5];
int nxt[MAXS + 5] = {0};
int lena = 0, lenb = 0;

inline void lowercase(char &ch){
    if (ch >= 'A' && ch <= 'Z')
        ch = ch - 'A' + 'a';
}

int main(){
    fgets(a, MAXS + 5, stdin);
    fgets(b, MAXS + 5, stdin);
    lena = strlen(a) - 1;
    lenb = strlen(b);
    for (int i = 0; i < lena; ++i)
        if (a[i] >= 'A' && a[i] <= 'Z')
            a[i] = a[i] - 'A' + 'a';
    for (int i = 0; i < lenb; ++i)
        if (b[i] >= 'A' && b[i] <= 'Z')
            b[i] = b[i] - 'A' + 'a';
    int pos = -1, ans = 0;
    nxt[0] = -1;
    int t = -1;
    for (int i = 1; i < lena; ++i){
        while (t > -1 && a[i] != a[t + 1])
            t = nxt[t];
        if (a[i] == a[t + 1])
            ++t;
        nxt[i] = t;
    }
    t = -1;
    for (int i = 0; i < lenb; ++i){
        while (t > -1 && a[t + 1] != b[i])
            t = nxt[t];
        if (a[t + 1] == b[i])
            ++t;
        if (t == lena - 1){
            if (ans == 0)
                pos = i - lena + 1;
            ++ans;
            t = nxt[t];
        }
    }
    if (ans == 0)
        cout << "-1" << '\n';
    else
        cout << ans << ' ' << pos << '\n';
    return 0;
}