模板题 hdu2222:

　　查询主串中出现过几种模式串。

1 #include 
      
        2 #define rep(i, a, b) for (int i = a; i <= b; i++) 3 #define REP(i, a, b) for (int i = a; i < b; i++) 4 #define drep(i, a, b) for (int i = a; i >= b; i--) 5 #define pb push_back 6 #define mp make_pair 7 #define clr(x) memset(x, 0, sizeof(x)) 8 #define travel(x) for (int i = G[x]; i; i = e[i].nx) 9 #define xx first10 #define yy second11 12 using namespace std;13 14 typedef long long i64;15 typedef pair
       
         pii;16 17 const int inf = ~0U >> 1;18 const i64 INF = ~0ULL >> 1;19 //***************************20 21 const int maxn = 100005;22 23 int fail[maxn], ndtot, tab[maxn];24 int ch[maxn][128];25 char s[10005];26 27 void add(char *str, int ha) {28     int p = 0;29     for (int i = 0; str[i]; i++) {30         if (!ch[p][str[i] - 32]) ch[p][str[i] - 32] = ++ndtot;31         p = ch[p][str[i] - 32];32     }33     tab[p] = ha;34 }35 36 int que[maxn];37 38 void build() {39     int qh(0), qt(0);40     que[++qt] = 0;41     while (qh != qt) {42         int x = que[++qh];43         REP(i, 0, 128) {44             if (ch[x][i]) {45                 que[++qt] = ch[x][i];46                 fail[ch[x][i]] = x ? ch[fail[x]][i] : 0;47             }48             else ch[x][i] = ch[fail[x]][i];49         }50     }51 }52 53 bool vis[505];54 55 int tot = 0, n;56 void query(char *str, int haha) {57     bool flag = false;58     clr(vis);59     int p = 0;60     for (int i = 0; str[i]; i++) {61         p = ch[p][str[i] - 32];62         int k = p;63         while (k) {64             if (tab[k]) vis[tab[k]] = 1, flag = 1;65             k = fail[k];66         }67     }68     if (flag) {69         printf("web %d:", haha);70         rep(i, 1, n) if (vis[i]) printf(" %d", i);71         tot++;72         puts("");73     }74 }75 76 int main() {77     scanf("%d", &n);78     rep(i, 1, n) { scanf("%s", s); add(s, i); }79     build();80     int m;81     scanf("%d", &m);82     tot = 0;83     rep(i, 1, m) {84         scanf("%s", s);85         query(s, i);86     }87     printf("total: %d\n", tot);88     return 0;89 }
       
      

　　

　　同类题 hdu2896:

　　　　也是查询主串中出现过几种模式串。

1 #include 
      
        2 #define rep(i, a, b) for (int i = a; i <= b; i++) 3 #define REP(i, a, b) for (int i = a; i < b; i++) 4 #define drep(i, a, b) for (int i = a; i >= b; i--) 5 #define pb push_back 6 #define mp make_pair 7 #define clr(x) memset(x, 0, sizeof(x)) 8 #define travel(x) for (int i = G[x]; i; i = e[i].nx) 9 #define xx first10 #define yy second11 12 using namespace std;13 14 typedef long long i64;15 typedef pair
       
         pii;16 17 const int inf = ~0U >> 1;18 const i64 INF = ~0ULL >> 1;19 //***************************20 21 const int maxn = 100005;22 23 int fail[maxn], ndtot, tab[maxn];24 int ch[maxn][128];25 char s[10005];26 27 void add(char *str, int ha) {28     int p = 0;29     for (int i = 0; str[i]; i++) {30         if (!ch[p][str[i] - 32]) ch[p][str[i] - 32] = ++ndtot;31         p = ch[p][str[i] - 32];32     }33     tab[p] = ha;34 }35 36 int que[maxn];37 38 void build() {39     int qh(0), qt(0);40     que[++qt] = 0;41     while (qh != qt) {42         int x = que[++qh];43         REP(i, 0, 128) {44             if (ch[x][i]) {45                 que[++qt] = ch[x][i];46                 fail[ch[x][i]] = x ? ch[fail[x]][i] : 0;47             }48             else ch[x][i] = ch[fail[x]][i];49         }50     }51 }52 53 bool vis[505];54 55 int tot = 0, n;56 void query(char *str, int haha) {57     bool flag = false;58     clr(vis);59     int p = 0;60     for (int i = 0; str[i]; i++) {61         p = ch[p][str[i] - 32];62         int k = p;63         while (k) {64             if (tab[k]) vis[tab[k]] = 1, flag = 1;65             k = fail[k];66         }67     }68     if (flag) {69         printf("web %d:", haha);70         rep(i, 1, n) if (vis[i]) printf(" %d", i);71         tot++;72         puts("");73     }74 }75 76 int main() {77     scanf("%d", &n);78     rep(i, 1, n) { scanf("%s", s); add(s, i); }79     build();80     int m;81     scanf("%d", &m);82     tot = 0;83     rep(i, 1, m) {84         scanf("%s", s);85         query(s, i);86     }87     printf("total: %d\n", tot);88     return 0;89 }
       
      

　　　　有一个需要注意的地方，这个题没有多组数据，然后如果写的是数组版，你对存储trie树的数组memset一遍就会mle，可能是如果不memset可以被编译器优化吧。。