DanganronpaTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 429Accepted Submission(s): 248
Problem Description
Danganronpa is a video game franchise created and developed by Spike Chunsoft, the series’ name is compounded from the Japanese words for "bullet" (dangan) and "refutation" (ronpa).Now, Stilwell is playing this game. There areverbal evidences, and Stilwell has"bullets". Stilwell will use these bullets to shoot every verbal evidence.Verbal evidences will be described as some strings, and bullets are some strings. The damage to verbal evidencefrom the bullet.
In other words,is equal to the times that stringappears as a substring in string.For example:Stilwell wants to calculate the total damage of each verbal evidenceafter shooting all, in other words is.
Input
The first line of the input contains a single number, the number of test cases.For each test case, the first line contains two integers.Nextlines, each line contains a string, describing a verbal evidence.Nextlines, each line contains a string, describing a bullet.For each test case,For all test case,consist of only lowercase English letters
Output
For each test case, outputlines, each line contains a integer describing the total damage offrom all.
Sample Input
15 6orzstokirigiridanganronpaooooookyoukodanganronpaoooooooooo
Sample Output
11037
Author
SXYZ
Source
题意：给n个母串，给m个匹配串，求每个母串依次和匹配串匹配，，能得到的数目和。
题解：AC自动机模板题
#include <stdio.h>#include <algorithm>#include <iostream>#include <string.h>#include <queue>using namespace std;struct Trie {int next[500010][26],fail[500010],end[500010];int root,L;int newnode() {for(int i = 0; i < 26; i++)next[L][i] = -1;end[L++] = 0;return L-1;}void init() {L = 0;root = newnode();}void insert(char buf[]) {int len = strlen(buf);int now = root;for(int i = 0; i < len; i++) {if(next[now][buf[i]-'a'] == -1)next[now][buf[i]-'a'] = newnode();now = next[now][buf[i]-'a'];}end[now]++;}void build() {queue<int>Q;fail[root] = root;for(int i = 0; i < 26; i++)if(next[root][i] == -1)next[root][i] = root;else {fail[next[root][i]] = root;Q.push(next[root][i]);}while( !Q.empty() ) {int now = Q.front();Q.pop();for(int i = 0; i < 26; i++)if(next[now][i] == -1)next[now][i] = next[fail[now]][i];else {fail[next[now][i]]=next[fail[now]][i];Q.push(next[now][i]);}}}int query(char buf[]) {int len = strlen(buf);int now = root;int res = 0;for(int i = 0; i < len; i++) {now = next[now][buf[i]-'a'];int temp = now;while( temp != root ) {res += end[temp];//end[temp] = 0;temp = fail[temp];}}return res;}void debug() {for(int i = 0; i < L; i++) {printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],end[i]);for(int j = 0; j < 26; j++)printf("%2d",next[i][j]);printf("]\n");}}};char buf[100010];int m;char s[605015];char c[10010];Trie ac;int main() { // freopen("test.in","r",stdin);int T;int n;scanf("%d",&T);while( T– ) {scanf("%d%d",&n,&m);ac.init();memset(s,0,sizeof s);int len=0;for(int i=0; i<n; i++) { ///把所有的串接起来，用空格隔开scanf("%s",c);int l=strlen(c);if(i!=0)s[len++]=' ';strcat(s,c);len+=l;}s[len]=' ';s[++len]=0;for(int i=0; i<m; i++) {scanf("%s",buf);ac.insert(buf);}ac.build();int l=0;while(l<len) {int k=0;while(s[l]!=' ') {///找到当前单词buf[k++]=s[l++];}buf[k]=0;l++;printf("%d\n",ac.query(buf));}}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
没有行李，没有背包，不带电脑更不要手机，
