简单的字符串模拟题

题目背景

一封好的情书需要撰写人全身心的投入。CYY同学看上了可爱的iuaa想对她表白，但却不知道自己写的情书是否能感动她，现在他带着情书请你来帮助他。

题目描述

为了帮助CYY，我们定义一个量化情书好坏的标准感动值。判断感动值的方法如下:

在情书的一句话中若含有给定词汇列表中的特定单词，则感动值加1，但每一单词在同一句话中出现多次感动值不叠加，不同单词不受影响。保证输入的单词不重复。
每句话以英文句号定界。
全文不区分大小写。

输入格式

第一行包含一个数字n，表示导致感动值提升的词汇列表中单词的数量，随后n行是给定单词，每行一个。保证单词只包含英文字母。

最后一行为情书正文，保证只包含以下几种字符: 英文字母、数字、空格、英文逗号、英文句号。

输出格式

一个数字g，表示情书带来的感动值。

Inputs and Outputs examples

Inputs’ e.g. #1

3
love
so
much
I love you so much.

Outputs e.g. #1

说明 / 提示

对于所有的数据，保证1 ≤ n,m,k ≤ 100，每个单词不超过50字符，全文不超过1000字符。

分析

Solution #1

简单AC自动机题目.

首先建立AC自动机,然后对于全文进行删除空格和不区分大小写处理.

然后以句号为界,每次把一个句子作为一个文本串,然后枚举一遍模式串,查询统计答案即可.

由于本题数据范围极小,这种做法理论上也是可以AC的.

Solution #2

首先对于原文进行删除空格和不区分大小写处理.

开一个map记录一下关键词,然后暴力枚举原文进行判断并统计答案即可.

需要注意细节,比如应忽略空格,逗号,句号.注意对于map的清零,等等.

代码 for Solution #2

/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<iostream>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?EOF:*is++;
    }
    inline int getint(){
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-'){
            neg = 1;ch = getch();
        }
        while(isdigit(ch)){
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--)	putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
const int MAXN = 1e2 + 10;
std::string a,b,make[MAXN];
std::map<std::string, bool> flag;
int n,ans;
/* functions */
using std::cin;
int main(int argc,char *argv[]){
	IOS(false); cin>>n;
	FOR(i,1,n,1)  cin>>make[i];
	getline(cin,a); getline(cin,b);
	FOR(i,1,n,1) {
		FOR(j,0,make[i].size() - 1,1)
			if(make[i][j] >= 'A' && make[i][j] <= 'Z') make[i][j] += 32;
	}
	FOR(i,0,b.size() - 1,1)
		if(b[i] >= 'A' && b[i] <= 'Z') b[i] += 32;
	FOR(j,1,n,1) {
		FOR(i,0,b.size() - 1,1) {
			if(b[i] == '.') flag.clear();
			if(b.substr(i,make[j].size()) == make[j]) {
				#define str b[i + make[j].size()]
				if(str == '.' || str == ',' || str == ' ') {
					if(flag[make[j]]) continue;
					flag[make[j]] = true; ans++;
				}
				#undef str
			}
		}
	}
	std::cout<<ans<<std::endl;
	return 0;
}

LuoguP2264题解