这道题居然可以用string暴力A掉…… 提交记录 内网OJ

// luogu-judger-enable-o2
#include <iostream>
#include <string>
#include <regex>
int cursor;
int operations, operationValue, textLength;
std::string text, operationType, operationText, finalText;
char currentChar;
int main() {
    std::ios::sync_with_stdio(false);
    std::cin >> operations;
    while (operations--) {
        std::cin >> operationType;
        if (operationType == "Move") {
            std::cin >> operationValue;
            cursor = operationValue;
        } else if (operationType == "Insert") {
            std::cin >> operationValue;
            finalText = "";
            textLength = 0;
            while (std::cin.get(currentChar)) {
                if (currentChar < 32 || currentChar > 126 || currentChar == '\n' || currentChar == '\r')
                    continue;
                ++ textLength;
                finalText += currentChar;
                if (textLength >= operationValue)
                    break;
            }
            text.insert(cursor, finalText);
        } else if (operationType == "Delete") {
            std::cin >> operationValue;
            text.erase(cursor, operationValue);
        } else if (operationType == "Get") {
            std::cin >> operationValue;
            std::cout << text.substr(cursor, operationValue) << std::endl;
        } else if (operationType == "Prev") {
            if (cursor)
                --cursor;
        } else if (operationType == "Next") {
            if (cursor < text.length())
            ++cursor;
        }
    }
    return 0;
}

题目描述
一般的文本编辑器都有查找单词的功能,该功能可以快速定位特定单词在文章中的位置,有的还能统计出特定单词在文章中出现的次数。
现在,请你编程实现这一功能,具体要求是:给定一个单词,请你输出它在给定的文章中出现的次数和第一次出现的位置。注意:匹配单词时,不区分大小写,但要求完全匹配,即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同(参见样例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 。
NOIp2011普及组第2题。

题解
本题较为简单的解法是逐项对比,同时也可以用Hash解法,这里阐述的即为Hash解法。
注意,测试样例时请自行去除行末的空格,题中已说明行末无空格。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef unsigned long long ULL;// 把unsigned long long简写
const int b=27;
const int MAXN=1000050;// 数组大小
string t1;// 输入的单词
string t2;// 输入的文章
char s1[MAXN];// 输入的单词
char s2[MAXN];// 输入的文章
long long power[MAXN];// 用来存放b&n
long long sum[MAXN];// 用来存放主串hash值
int main() {
    int i,pos=-1;// 第一次出现的位置,如果没有就是-1
    power[0]=1;// b^0=1
    for (int i=1;i<MAXN;++i)// 计算MAXN次
        power[i]=power[i-1]*b;// 计算b*n
    getline(cin,t1);// 用getline读入一整行
    getline(cin,t2);// 用getline读入一整行
    int s1len=t1.length(),s2len=t2.length();// 存放长度
    for (int i=0;i<s1len;i++) s1[i+1]=tolower(t1[i]);// 放进s1数组并转换大小写,注意这里往后移了一位
    for (int i=0;i<s2len;i++) s2[i+1]=tolower(t2[i]);// 放进s2数组并转换大小写,注意这里往后移了一位
    sum[0]=0;// 初始化
    for (int i=1;i<=s2len;++i)
        sum[i]=sum[i-1]*b+s2[i];// 计算主串hash值
    ULL s=0;// 用来存放子串hash值
    for (int i=1;i<=s1len;++i)
        s=s*b+s1[i];// 计算子串hash值
    int tot=0;// 计数器
    for (int i=0;i<=s2len-s1len;++i)
        if(s==sum[i+s1len]-sum[i]*power[s1len]&&(i==0||s2[i]==' ')&&(i+s1len==s2len||s2[i+s1len+1]==' '))// 如果hash值匹配,并且这个词前后是空格(或者在文章开头/结尾)
        {
            if (pos==-1) pos=i;// 如果是第一个,保存位置
            ++tot;// 总词数加1
        }
    if (pos==-1) cout<<-1;// 没有找到,输出-1
    else cout<<tot<<' '<<pos<<endl;// 输出次数、位置
    return 0;// 结束程序
}