很簡單的Trie樹，記錄每個前綴的次數，dfs一次Trie即可

#include<set> #include<map> #include<list> #include<stack> #include<queue> #include<cmath> #include<ctime> #include<cstdio> #include<string> #include<vector> #include<cstring> #include<cstdlib> #include<sstream> #include<iostream> #include<algorithm> using namespace std; #define LL long long #define INF 0x7fffffff #define debug cout << "here" << endl #define CLR(X, Y) memset(X, Y sizeof Y) #define FOR(X, Y) for(int i = X;i < Y;i ++) inline int myMin(int x, int y){return x < y ? x : y;} inline int myMax(int x, int y){return x < y ? y : x;} struct Node{int cnt;Node* child[4];Node(){cnt = 0;for(int i = 0;i < 4;i ++) child[i] = NULL;} }; int ans; Node *root; int Hash(char c){if(c == 'A') return 0;if(c == 'G') return 1;if(c == 'C') return 2;if(c == 'T') return 3; }void insert(char* str){Node *tmp = root;while(str[0]){int idx = Hash(str[0]);if(tmp->child[idx] == NULL) tmp->child[idx] = new Node();tmp = tmp->child[idx];tmp->cnt ++;str++;} }void dfs(int dep, Node *tmp){if(dep*tmp->cnt > ans) ans = dep*tmp->cnt;for(int i = 0;i < 4;i ++){if(tmp->child[i]) dfs(dep+1, tmp->child[i]);} }int main(int argc, char* argv[]){char str[55];int t, n, CASE(0);// freopen("in.cpp", "r", stdin);scanf("%d", &t);while(t--){root = new Node();scanf("%d", &n);for(int i = 0;i < n;i ++){scanf("%s", str);insert(str);}ans = 0;dfs(0, root);printf("Case %d: %d\n", ++CASE, ans);}return 0; }
樹即可，

轉載于:https://www.cnblogs.com/wangzhili/p/3950200.html

總結

以上是生活随笔為你收集整理的lightoj 1224的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。