中文題，題意就不解釋了。
這道題把我坑了下，應該是做題不仔細的原因，一開始我以為是26個字母的（沒認真讀題，看樣例的結果） ，然後RE了好幾發，最多發現題目裡的描述是ASCLL碼表裡面的可見字符，然後將建字典樹過程中的0 - 25的循環改成0 - 127 就過了。
講一下思路，這道題就是AC自動機的模版題，唯一需要注意的就是加一個id的域來存這個字符串的序號，最後輸出的時候要按從小到大的順序，我直接全部扔進set輸出了。
不過我感覺數據有點水啊。。。總感覺A的不是很踏實。
加了釋放內存，但是發現內存沒比原來的少，難道數據只有一組o(︶︿︶)o
#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[128] ;
int count ;
int id ;
node() {
fail = 0 ;
count = 0 ;
mem(next , 0) ;
id = 0 ;
}
}*qe[1000005] ;
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] ;
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 < 128 ; 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] ;
}
}
}
}
set<int>anss[1111] ;
int search(char *a ,int id) {
int l = strlen(a) ;
node *p = root ;
int ans = 0 ;
for (int i = 0 ; i < l ; i ++ ) {
int tt = a[i] ;
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[id].insert(temp -> id) ;
//temp -> count = -1 ;
temp = temp -> fail ;
}
}
return ans ;
}
void deleteAll(node *p){
for (int i = 0 ; i < 128 ; i ++ )
if(p -> next[i] != 0){
deleteAll(p -> next[i]) ;
}
delete p ;
}
char a[11111] ;
int num[1111] ;
int main() {
int n ;
cin >> n ;
getchar() ;
root = new node() ;
for (int i = 1 ; i <= n ;i ++ ){
gets(a) ;
insert(a ,i ) ;
}
int m ;
cin >> m ;
getchar() ;
build() ;
for (int i = 1 ; i <= m ;i ++ ){
gets(a) ;
num[i] = search(a , i) ;
}
int cc = 0 ;
for (int i = 1 ; i <= m ;i ++ ){
if(num[i]){
printf("web %d:",i) ;
for(set<int>::iterator p = anss[i].begin() ; p != anss[i].end() ; ++ p)
cout <<" "<< *p ;
cc ++ ;
puts("") ;
}
}
printf("total: %d\n",cc) ;
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[128] ;
int count ;
int id ;
node() {
fail = 0 ;
count = 0 ;
mem(next , 0) ;
id = 0 ;
}
}*qe[1000005] ;
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] ;
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 < 128 ; 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] ;
}
}
}
}
set<int>anss[1111] ;
int search(char *a ,int id) {
int l = strlen(a) ;
node *p = root ;
int ans = 0 ;
for (int i = 0 ; i < l ; i ++ ) {
int tt = a[i] ;
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[id].insert(temp -> id) ;
//temp -> count = -1 ;
temp = temp -> fail ;
}
}
return ans ;
}
void deleteAll(node *p){
for (int i = 0 ; i < 128 ; i ++ )
if(p -> next[i] != 0){
deleteAll(p -> next[i]) ;
}
delete p ;
}
char a[11111] ;
int num[1111] ;
int main() {
int n ;
cin >> n ;
getchar() ;
root = new node() ;
for (int i = 1 ; i <= n ;i ++ ){
gets(a) ;
insert(a ,i ) ;
}
int m ;
cin >> m ;
getchar() ;
build() ;
for (int i = 1 ; i <= m ;i ++ ){
gets(a) ;
num[i] = search(a , i) ;
}
int cc = 0 ;
for (int i = 1 ; i <= m ;i ++ ){
if(num[i]){
printf("web %d:",i) ;
for(set<int>::iterator p = anss[i].begin() ; p != anss[i].end() ; ++ p)
cout <<" "<< *p ;
cc ++ ;
puts("") ;
}
}
printf("total: %d\n",cc) ;
deleteAll(root) ;
return 0 ;
}
