萌萌哒的链接:?id=2945
题目的意思就是找每一个字符串出现的次数,输出出现1-n次的字符串的个数.
字典树的哈希应用.index记录相同字符串出现的次数,最后dfs查找. 因为题目中只有4个字母,所以dfs总的时间复杂度
为4*字典树的总结点个数.
字典树用链表写挺方便的,就是内存花销太大,比如这道题目如果把内存开成26,就MLE了.
#include <iostream>#include <cstring>#include <cstdio>#include <cmath>#include <set>#include <map>#include <queue>#include <vector>#include <cstdlib>#include <algorithm>#define ls u << 1#define rs u << 1 | 1#define lson l, mid, u << 1#define rson mid + 1, r, u << 1 | 1#define INF 0x3f3f3f3f#define MAX 4using namespace std;typedef long long ll;const int M = 2e4 + 100;const int mod = 2147483647;char s[25];int num[M],d[] = {'A'-'A','C'-'A','T'-'A','G'-'A'};struct Trie {int index;Trie *next[MAX];Trie() {index = 0;memset(next,0,sizeof(next));}};void Trie_insert(Trie *tr,int len) {if(s[len]) {int u = s[len] – 'A';for(int i = 0; i < 4; i++){if(u == d[i]){u = i;break;}}if(s[len + 1] == '\0' && tr->next[u]) {tr->next[u]->index++;return ;}if(tr->next[u] == 0) tr->next[u] = new Trie;Trie_insert(tr->next[u],len + 1);} else {tr->index = 1;}}void dfs(Trie *tr) {if(tr->index) num[tr->index]++;for(int u = 0; u < 4; u++) {if(tr->next[u]) dfs(tr->next[u]);}}void deal_Trie(Trie *tr){if(tr == NULL) return ;for(int u = 0; u < 4; u++){if(tr->next[u]) dfs(tr->next[u]);}free(tr);}int main() {int n,m;while(~scanf("%d %d",&n,&m) && (n | m)) {Trie *root = new Trie;memset(num,0,sizeof(num));for(int i = 0; i < n; i++) {scanf("%s",s);Trie_insert(root,0);}dfs(root);for(int i = 1; i <= n; i++) {printf("%d\n",num[i]);}//deal_Trie(root);}return 0;}
，放下一种执着，收获一种自在。放下既是一种理性抉择，也是一种豁达美。
