P2105?背單詞From:?dogther 時(shí)間: 1000ms / 空間: 131072KiB / Java類名: Main

背景

小明對(duì)英語一竅不通，令老師十分頭疼。于是期末考試前夕，為了班級(jí)的及格率，小明被逼著開始背單詞……

描述

老師給了小明一篇長度為N的英語文章，然后讓小明背M個(gè)單詞。為了確保小明不會(huì)在背單詞時(shí)睡著，老師會(huì)向他提Q個(gè)問題，每次老師選擇一個(gè)區(qū)間L..R，小明要回答在這段文字中他背過的單詞總共出現(xiàn)過多少次。

輸入格式

第一行兩個(gè)整數(shù)M、Q如前所述。第二行為英語文章。接下來M行每行一個(gè)需要背的單詞。接下來Q行每行一個(gè)詢問，包含兩個(gè)整數(shù)L、R（含端點(diǎn)），即給定的文字區(qū)間。

輸出格式

Q行，對(duì)每個(gè)詢問輸出一行表示答案。

測試樣例1

輸入

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

輸出

2?
0?
5

備注

數(shù)據(jù)范圍：
對(duì)于30%的數(shù)據(jù)，1<=N<=10^3,1<=Q<=10^3
對(duì)于60%的數(shù)據(jù)，1<=N<=10^5,1<=Q<=10^5
對(duì)于100%的數(shù)據(jù)，1<=N<=5*10^5,1<=M<=10,1<=Q<=5*10^5,1<=每個(gè)單詞的長度<=N,1<=L<=R<=N
提示：數(shù)據(jù)較大，請(qǐng)大家盡量采取高效率的讀入輸出方法。

/============================================================================ // 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; }

總結(jié)

以上是生活随笔為你收集整理的P2105 背单词的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。