說一下這題要注意的地方，因為目標串裡面有不是大寫字母的字符，所以每次進行匹配的時候要判斷一下，如果不是大寫字母就continue掉，注意此時要把P指針指向根節點。
其他就沒什麼了，就是模版AC自動機。
對了，還有就是題目是多組輸入。。。。。。WA的少年趕緊去改掉。。目測就能過了。。
更新了刪除節點，釋放內存，因為做到一道題目不釋放內存會MLE，所以把這裡前面的代碼也加進去，方便以後整理模版。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2505
#define inf 1<<28
#define LL(x) ( x << 1 )
#define RR(x) ( x << 1 | 1 )
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define PII pair<int,int>
using namespace std;
struct node {
node *fail ;
node *next[26] ;
int count ;
int id ;
node() {
fail = 0 ;
count = 0 ;
mem(next , 0) ;
id = 0 ;
}
}*qe[5000005] ;
node *root = 0 ;
//insert a[] .
void insert(char *a ,int id) {
node *p = root ;
int l = strlen(a) ;
for (int i = 0 ; i < l ; i ++ ) {
int tt = a[i] - 'A' ;
if(p -> next[tt] == 0) {
p -> next[tt] = new node() ;
}
p = p -> next[tt] ;
}
p -> count ++ ;
p -> id = id ;
}
//build *fail .
void build() {
root -> fail = 0 ;
int h = 0 , t = 0 ;
qe[h ++ ] = root ;
while(h > t) {
node *temp = qe[t ++ ] ;
node *p = 0 ;
for (int i = 0 ; i < 26 ; i ++ ) {
if(temp -> next[i] != 0) {
if(temp == root)temp -> next[i] -> fail = root ;
else {
p = temp -> fail ;
while(p != 0) {
if(p -> next[i] != 0) {
temp -> next[i] -> fail = p -> next[i] ;//找到匹配
break ;
}
p = p -> fail ;
}
if(p == 0)temp -> next[i] -> fail = root ;//如果沒找到，則將fail指向root
}
qe[h ++ ] = temp -> next[i] ;
}
}
}
}
int anss[1111] ;
int search(char *a) {
int l = strlen(a) ;
node *p = root ;
int ans = 0 ;
for (int i = 0 ; i < l ; i ++ ) {
int tt = a[i] - 'A' ;
if(tt < 0 || tt >= 26){
p = root ;
continue ;
}
while(p -> next[tt] == 0 && p != root)p = p -> fail ;
p = p -> next[tt] ;
p = (p == 0) ? root : p ;
node *temp = p ;
while(temp != root && temp -> count != 0) {
ans += temp -> count ;
anss[temp -> id] ++ ;
//temp -> count = -1 ;
temp = temp -> fail ;
}
}
return ans ;
}
char a[1111][55] ;
char b[2000005] ;
void deleteAll(node *p){
for (int i = 0 ; i < 26 ;i ++ ){
if(p -> next[i] != 0){
deleteAll(p -> next[i]) ;
}
}
delete p ;
}
int main() {
int n ;
while(cin >> n ) {
mem(anss, 0) ;
root = new node() ;
for (int i = 1 ; i <= n ; i ++ ) {
scanf("%s",a[i]) ;
insert(a[i] , i) ;
}
build() ;
scanf("%s",b) ;
search(b) ;
for (int i = 1 ; i <= n ; i ++ ) {
if(anss[i]) {
cout << a[i] << ": " << anss[i] << endl;
}
}
deleteAll(root) ;
}
return 0 ;
}
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2505
#define inf 1<<28
#define LL(x) ( x << 1 )
#define RR(x) ( x << 1 | 1 )
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define PII pair<int,int>
using namespace std;
struct node {
node *fail ;
node *next[26] ;
int count ;
int id ;
node() {
fail = 0 ;
count = 0 ;
mem(next , 0) ;
id = 0 ;
}
}*qe[5000005] ;
node *root = 0 ;
//insert a[] .
void insert(char *a ,int id) {
node *p = root ;
int l = strlen(a) ;
for (int i = 0 ; i < l ; i ++ ) {
int tt = a[i] - 'A' ;
if(p -> next[tt] == 0) {
p -> next[tt] = new node() ;
}
p = p -> next[tt] ;
}
p -> count ++ ;
p -> id = id ;
}
//build *fail .
void build() {
root -> fail = 0 ;
int h = 0 , t = 0 ;
qe[h ++ ] = root ;
while(h > t) {
node *temp = qe[t ++ ] ;
node *p = 0 ;
for (int i = 0 ; i < 26 ; i ++ ) {
if(temp -> next[i] != 0) {
if(temp == root)temp -> next[i] -> fail = root ;
else {
p = temp -> fail ;
while(p != 0) {
if(p -> next[i] != 0) {
temp -> next[i] -> fail = p -> next[i] ;//找到匹配
break ;
}
p = p -> fail ;
}
if(p == 0)temp -> next[i] -> fail = root ;//如果沒找到，則將fail指向root
}
qe[h ++ ] = temp -> next[i] ;
}
}
}
}
int anss[1111] ;
int search(char *a) {
int l = strlen(a) ;
node *p = root ;
int ans = 0 ;
for (int i = 0 ; i < l ; i ++ ) {
int tt = a[i] - 'A' ;
if(tt < 0 || tt >= 26){
p = root ;
continue ;
}
while(p -> next[tt] == 0 && p != root)p = p -> fail ;
p = p -> next[tt] ;
p = (p == 0) ? root : p ;
node *temp = p ;
while(temp != root && temp -> count != 0) {
ans += temp -> count ;
anss[temp -> id] ++ ;
//temp -> count = -1 ;
temp = temp -> fail ;
}
}
return ans ;
}
char a[1111][55] ;
char b[2000005] ;
void deleteAll(node *p){
for (int i = 0 ; i < 26 ;i ++ ){
if(p -> next[i] != 0){
deleteAll(p -> next[i]) ;
}
}
delete p ;
}
int main() {
int n ;
while(cin >> n ) {
mem(anss, 0) ;
root = new node() ;
for (int i = 1 ; i <= n ; i ++ ) {
scanf("%s",a[i]) ;
insert(a[i] , i) ;
}
build() ;
scanf("%s",b) ;
search(b) ;
for (int i = 1 ; i <= n ; i ++ ) {
if(anss[i]) {
cout << a[i] << ": " << anss[i] << endl;
}
}
deleteAll(root) ;
}
return 0 ;
}
