星球的身份证是一个位的字符串。每位只包含''~''。上面包含了个人信息。并且根据个人的身份证可以知道个人的相似度。相似度:个人身份证的最长公共前缀的长度。假如和的相似度为。那么A和B的身份证的前面位是相同的,并且第位一定不同。没有两个人的身份证是完全相同的。现在有一个身份证库,保存有个人的身份证帐号。
有个询问。每个询问给出一个人的身份证,询问身份证库的人和这个人最大的相似度,并且询问身份证库有多少个人和他的相似度等于这个最大相似度。
星球的身份证是一个位的字符串。每位只包含''~''。上面包含了个人信息。并且根据个人的身份证可以知道个人的相似度。相似度:个人身份证的最长公共前缀的长度。假如和的相似度为。那么A和B的身份证的前面位是相同的,并且第位一定不同。没有两个人的身份证是完全相同的。现在有一个身份证库,保存有个人的身份证帐号。
一行:
行:每行一个长度为位的字符串(身份证库里的身份证,保证没有相同的身份证)(每位只包含''~'')
行:每行一个长度为位的字符串 (代表每个询问)
对于每个询问:输出身份证库的人和这个人最大的相似度,并且输出身份证库有多少个人和他的相似度等于这个最大相似度。(两个整数,用空格隔开)
3 2 333333333333333333 111111122222222222 111111133333333333 111111111000000000 000000000000000000
7 2 0 3
111111111000000000和111111122222222222,111111133333333333相似度都是7,并且7是最大的相似度。000000000000000000和身份证库的人相似度都为0。并且0是最大的相似度。
#include<bits/stdc++.h> using namespace std; struct TrieNode { int k; // 相似度 int val; // 是几个字符串的前缀 vector<TrieNode*> children; TrieNode(int _k): k(_k), val(0), children(10) {} }; TrieNode* root; void insert(string& s) { TrieNode* p = root; p->val++; for (auto c : s) { int x = c - '0'; if (!p->children[x]) { p->children[x] = new TrieNode(p->k + 1); } p = p->children[x]; p->val++; } } TrieNode* query(string& s) { TrieNode* p = root; for (auto c : s) { int x = c - '0'; if (!p->children[x]) break; p = p->children[x]; } return p; } int main() { root = new TrieNode(0); int n, Q; cin >> n >> Q; string s; TrieNode* p = nullptr; for (int i = 0; i < n; i++) { cin >> s; insert(s); } for (int i = 0; i < Q; i++) { cin >> s; p = query(s); cout << p->k << " " << p->val << endl; } return 0; }字典树,结点存相似度和有多少个字符串经过该节点。
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] params = br.readLine().split(" "); int n = Integer.parseInt(params[0]); int q = Integer.parseInt(params[1]); Trie trie = new Trie(); while(n-- > 0){ trie.add(br.readLine()); } while(q-- > 0){ int[] res = trie.search(br.readLine()); System.out.println(res[0] + " " + res[1]); } } } class Node { public Node[] next = new Node[10];; public int pass = 0; public boolean end = false; } class Trie { Node root; int size; public Trie() { root = new Node(); size = 0; } public void add(String seq) { Node cur = root; for(int i = 0; i < seq.length(); i++){ int index = seq.charAt(i) - '0'; if(cur.next[index] == null){ cur.next[index] = new Node(); } cur = cur.next[index]; cur.pass++; } cur.end = true; size++; } public int[] search(String seq) { Node cur = root; int len = 0; for(int i = 0; i < seq.length(); i++){ int index = seq.charAt(i) - '0'; if(cur.next[index] == null){ break; } cur = cur.next[index]; len++; } return len == 0? new int[]{len, size}: new int[]{len, cur.pass}; } }
哈希表来剔除前缀不一致的字符串,但是超时 #include <iostream> #include <bits/stdc++.h> using namespace std; int main() { int n,Q; cin>>n>>Q; vector<string> data(n); vector<string> query(Q); for(int i = 0;i<n;i++) { cin>>data[i]; } for(int i = 0;i<Q;i++) { cin>>query[i]; } unordered_map<int,bool> maps(n); for(int q=0;q<Q;q++) { int length=0; int last_number = 0; unordered_map<int,bool> temp_maps = maps; for (int i=0;i<18;i++) { bool flag = false; int numbers = 0; for(int j=0;j<n;j++) { if(temp_maps[j]==true) continue; if(data[j][i]==query[q][i])//前面已经不相等不应该继续判断 { flag = true; numbers++; } else temp_maps[j]=true; } if(flag == true) { last_number = numbers; length++; } else break; } if(last_number==0) cout<<length<<" "<<n<<endl; else cout<<length<<" "<<last_number<<endl; } } // 64 位输出请用 printf("%lld")
import java.util.ArrayList; import java.util.List; import java.util.Scanner; //主要是性能问题,实现的话不难,暴力耗时巨大,所以相当于建了索引的方式,测试用例全通过 public class Main{ public static Node root = new Node(); public static void main(String[] args) { Scanner input = new Scanner(System.in); String s = input.nextLine().trim(); String[] a = s.split(" "); int n = Integer.parseInt(a[0]); int q = Integer.parseInt(a[1]); String[] datas = new String[n]; for(int i = 0;i < n;i++){ String s1 = input.nextLine(); datas[i] = s1; } String[] target = new String[q]; for(int i = 0;i < q;i++){ String s1 = input.nextLine(); target[i] = s1; } for(int i = 0;i < n;i++){ insertNode(datas[i],root); } for(int i = 0;i < q;i++){ R r = solve(target[i]); System.out.println(r.similar + " " + r.number); } } public static R solve(String s) { int similar = 0; R r = find(0, s, root, similar); return r; } public static R find(int i,String s,Node node,int similar){ R r; int index = s.charAt(i) - '0'; if(node.child[index] != null){ similar++; r = find(i + 1, s, node.child[index], similar); }else{ return null; } if(r == null) { r = new R(); r.similar = similar; r.number = node.child[index].count; } return r; } public static void insertNode(String s,Node node){ insert(0,s,node); } public static void insert(int i,String s,Node node){ if(i == s.length()){ return; } int index = s.charAt(i) - '0'; if(node.child[index] == null){ node.child[index] = new Node(); } node.child[index].count++; insert(i + 1,s,node.child[index]); } static class Node{ public int count; public Node[] child = new Node[10]; public Node(){ } } static class R{ public int similar; public int number; } }
#include <iostream> #include <set> #include <vector> using namespace std; int GetSameLength(const char* p1, const char* p2){ int s = 0; while (*p1 != '\0' && *p2 != '\0') { if(*p1 == *p2){ s++; p1++; p2++; }else{ break; } } return s; } int main(){ int n, q; cin>>n>>q; set<string> idSet; //map<string, string> sMap; for(int i=0; i<n; i++){ string tmpStr; cin>>tmpStr; idSet.insert(tmpStr); } vector<pair<int, int>> resVec; for(int i=0; i<q; i++){ string tmpQstr; cin>>tmpQstr; auto iter = idSet.insert(tmpQstr); auto iter1 = iter.first; pair<int, int> pair1, pair2; if(iter1 != idSet.begin()){ --iter1; int s = GetSameLength(tmpQstr.c_str(), iter1->c_str()); int sum = 1; while (iter1 != idSet.begin()) { --iter1; int curS = GetSameLength(tmpQstr.c_str(), iter1->c_str()); if(s == curS){ sum++; }else{ break; } } pair1 = pair<int, int>(s, sum); } else{ pair1 = pair<int, int>(0, 0); } int s = 0; int sum = 0; auto iter2 = iter.first; ++iter2; while (iter2 != idSet.end()) { int curS = GetSameLength(tmpQstr.c_str(), iter2->c_str()); if(curS < s){ break; } else{ s = curS; sum++; ++iter2; } } pair2 = pair<int, int>(s, sum); if(pair1.first == pair2.first){ resVec.push_back(pair<int, int>(pair1.first, pair1.second + pair2.second)); } else if(pair1.first > pair2.first){ resVec.push_back(pair1); } else{ resVec.push_back(pair2); } idSet.erase(iter.first); } for(int i=0; i<q; i++){ cout<<resVec[i].first<<" "<<resVec[i].second<<endl; } return 0; }
import java.util.*; import java.io.*; public class Main{ static class Node{ Node[] children = new Node[10]; int n = 0; int deep = 0; public Node(int n, int deep) { this.n = n; this.deep = deep; } } static Node root = new Node(0,0); static void insert(String ss){ char[] arr = ss.toCharArray(); Node _temp = root; for (int i = 0;i<arr.length;i++){ if(_temp.children[arr[i] - '0'] == null) _temp.children[arr[i] - '0'] = new Node(1,_temp.deep+1); else _temp.children[arr[i] - '0'].n ++; _temp = _temp.children[arr[i] - '0']; } } static void search(String ss){ char[] arr = ss.toCharArray(); Node _temp = root; for (int i = 0;i<arr.length;i++){ if(_temp.children[arr[i] - '0'] != null){ _temp = _temp.children[arr[i] - '0']; }else { System.out.println(_temp.deep+" "+_temp.n); break; } } } public static void main(String[] args) throws IOException{ BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(reader.readLine()); int n = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); while (n-- > 0){ root.n ++; insert(reader.readLine()); } while (q-- > 0){ search(reader.readLine()); } reader.close(); } }
#include <iostream> #include <cstring> #include <algorithm> #include <unordered_map> using namespace std; const int N = 1e7+5; int trie[N][10] , cnt[N]; int n, m, idx , nn; string str; void insert(string str){ int p = 0 ; for(int i = 0; i<str.size(); i++){ int u = str[i] - '0'; if(!trie[p][u]) trie[p][u] = ++idx; p = trie[p][u]; cnt[p]++; } } int search(string str , int &ans){ int p = 0; for(int i = 0; i<str.size(); i++){ int u = str[i] - '0'; if(!trie[p][u]) return i ; ans = cnt[trie[p][u]]; p = trie[p][u]; } return str.size() ; } int main() { cin>>n>>m; nn = n; while(n--){ cin>>str; insert(str); } while (m -- ){ cin>>str; int ans = 0; int res = search(str , ans); if(res == 0) cout<<res<<" "<<nn<<endl; else cout<<res<<" "<<ans<<endl; } return 0; }
import java.util.Scanner; import java.util.List; import java.util.ArrayList; public class Main { private static Node root = new Node(); public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String firstLine = scanner.nextLine(); String[] nums = firstLine.split(" "); for (int i=0; i<Integer.parseInt(nums[0]); i++) { putId(scanner.nextLine()); } for (int i=0; i<Integer.parseInt(nums[1]); i++) { get(scanner.nextLine()); } } private static void get(String id) { Node node = root; for (int i=0; i<id.length(); i++) { boolean flag = false; for (Node childNode : node.nodeList) { if (childNode.c == id.charAt(i)) { flag = true; node = childNode; break; } } if (!flag) { System.out.println(i + " " + node.count); break; } } } private static void putId(String id) { dfs(root, id, 0); } private static void dfs(Node node, String id, int index) { if (index < id.length()) { boolean flag = false; for (Node childNode : node.nodeList) { if (childNode.c == id.charAt(index)) { flag = true; childNode.count++; dfs(childNode, id, index + 1); break; } } if (!flag) { Node newNode = new Node(id.charAt(index), 1); node.nodeList.add(newNode); dfs(newNode, id, index + 1); } } } public static class Node { char c; int count; List<Node> nodeList; public Node() { this.nodeList = new ArrayList<>(); } public Node(char c, int count) { this.c = c; this.count = count; this.nodeList = new ArrayList<>(); } } }