P2105 背单词

P2105 背单词From: dogther 时间: 1000ms / 空间: 131072KiB / Java类名: Main

背景

小明对英语一窍不通，令老师十分头疼。于是期末考试前夕，为了班级的及格率，小明被逼着开始背单词……

描述

老师给了小明一篇长度为N的英语文章，然后让小明背M个单词。为了确保小明不会在背单词时睡着，老师会向他提Q个问题，每次老师选择一个区间L..R，小明要回答在这段文字中他背过的单词总共出现过多少次。

输入格式

第一行两个整数M、Q如前所述。第二行为英语文章。接下来M行每行一个需要背的单词。接下来Q行每行一个询问，包含两个整数L、R（含端点），即给定的文字区间。

输出格式

Q行，对每个询问输出一行表示答案。

测试样例1

输入

3 3 
ababaca 
c 
ba 
aba 
1 3 
3 4 
1 7

输出

2 
0 
5

备注

数据范围：
对于30%的数据，1<=N<=10^3,1<=Q<=10^3
对于60%的数据，1<=N<=10^5,1<=Q<=10^5
对于100%的数据，1<=N<=5*10^5,1<=M<=10,1<=Q<=5*10^5,1<=每个单词的长度<=N,1<=L<=R<=N
提示：数据较大，请大家尽量采取高效率的读入输出方法。

/============================================================================ // Name : beidanci.cpp // Author : judyge // Version : // Copyright : Your copyright notice // Description : Hello World in C++, Ansi-style //============================================================================#include <iostream> #include <map> #include <string> using namespace std;int main() {int m;int q;cin>>m>>q;char *p;cin>>p;char *s[m];for(int i=0;i<m;i++){cin>>s[i];}while(q--) { int l,r; cin>>l>>r;map<string, int> mapSubstr;map <string, int>::iterator iter;for(int i=l;i<r;i++) {for(int j=i;j<r;j++){string subs(&p[i],&p[j]);mapSubstr[subs]++;} }for(iter = mapSubstr.begin(); iter != mapSubstr.end(); iter++) {for(int i=0;i<m;i++){if(iter->first==s[i]){cout<<iter->second;}} }}return 0; }

总结

以上是生活随笔为你收集整理的P2105 背单词的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。