统计难题

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131070/65535 K (Java/Others)

Total Submission(s): 16945    Accepted Submission(s): 7292

Problem Description

Ignatius近期遇到一个难题,老师交给他非常多单词(仅仅有小写字母组成,不会有反复的单词出现),如今老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).

 

Input

输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每一个提问都是一个字符串.

注意:本题仅仅有一组測试数据,处理到文件结束.

 

Output

对于每一个提问,给出以该字符串为前缀的单词的数量.

 

Sample Input

banana

band

bee

absolute

acm

ba

b

band

abc

 

Sample Output

2

3

1

0

 

Author

Ignatius.L

入门题

#include

#include

#include

#include

#include

#include

#include

using namespace std;

const int maxn = 500000;

int ch[maxn][26];

int cnt;

int val[maxn];

inline int getIdx(char a){

return a-'a';

}

void init(){

memset(ch[0],0,sizeof ch[0]);

cnt = 1;

memset(val,0,sizeof val);

}

void insert(string st){

int u = 0;

for(int i = 0; i < st.size(); i++){

int k = getIdx(st[i]);

if(!ch[u][k]){

ch[u][k] = cnt;

val[cnt]++;

cnt++;

}else{

val[ch[u][k]]++;

}

u = ch[u][k];

}

}

int query(string st){

int u = 0;

for(int i = 0; i < st.size(); i++){

int k = getIdx(st[i]);

if(!ch[u][k]) return 0;

u = ch[u][k];

}

return val[u];

}

int main(){

string st;

init();

while(getline(cin,st)&&st.size()){

insert(st);

}

while(cin >> st){

cout<

}

return 0;

}

查看原文