首页 > 试题广场 >

身份证

[编程题]身份证

热度指数：856 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$X$ 星球的身份证是一个 $18$ 位的字符串。每位只包含' $0$ '~' $9$ '。上面包含了个人信息。并且根据 $2$ 个人的身份证可以知道 $2$ 个人的相似度。相似度： $2$ 个人身份证的最长公共前缀的长度。假如 $A$ 和 $B$ 的相似度为 $k$ 。那么A和B的身份证的前面 $k$ 位是相同的，并且第 $k+1$ 位一定不同。没有两个人的身份证是完全相同的。现在有一个身份证库，保存有 $n$ 个人的身份证帐号。

有 $Q$ 个询问。每个询问给出一个人的身份证，询问身份证库的人和这个人最大的相似度，并且询问身份证库有多少个人和他的相似度等于这个最大相似度。

输入描述:

一行： $n, Q(1<=n, q<=10^5)$

$n$ 行：每行一个长度为 $18$ 位的字符串（身份证库里的身份证，保证没有相同的身份证）（每位只包含' $0$ '~' $9$ '）

$Q$ 行：每行一个长度为 $18$ 位的字符串（代表每个询问）

输出描述:

对于每个询问：输出身份证库的人和这个人最大的相似度，并且输出身份证库有多少个人和他的相似度等于这个最大相似度。（两个整数，用空格隔开）

示例1

输入

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;
}

字典树，结点存相似度和有多少个字符串经过该节点。

发表于 2021-07-16 19:57:20 回复(4)

pein531

Trie字典树

很简单，实现一个非完全版（无删除功能）的Trie树就可以实现这个功能。对于每个节点，用一个pass变量记录经过这个节点的身份证号有多少个。这样，在search阶段就可以通过这个值快速获取到某个前缀的身份证号有多少个。而对本题而言，我们只需要在找不到更长的前缀时返回长度和前缀个数就好；如果是身份证号的开头数字就匹配不上，返回的前缀个数就是库内所有的身份证号。

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};
    }
}

发表于 2022-01-22 18:40:50 回复(0)

onceday

******纯c代码实现************

此题关键在于建立有序的索引，由于数据量较大，所以下意识就会考虑用空间换速度。

本题后续有大量查找，建立树结构是一种不错的选择。

由题可知，每个树都有十个子树，所以对于每个结点，都有十个子树，子树指针为空表明后续没有数据，即沿某一路经到达深度18层，则表明有一条数据。

本题还要求相似度相同的数目，可在树的每个结点附带一个累积量，记录建立此树的时候，访问该结点的次数，很明显，该次数对应此共同前缀对应的所有数据数，于是本题要求的所有信息在树2查找2的过程中可轻松得到。

代码如下：

#include <stdio.h>

#include <stdlib.h>

typedef struct __data
{
int amount[10];
struct __data* next[10];
}_data;

_data* new_data(void);
void get_data(_data* data,int num);
void find_data(_data* data,int (*dout)[2],int qnum);

int main(void)
{
int num=0;
int qnum=0;
int out[100000][2];
_data data={{0},{NULL}};
scanf("%d %d",&num,&qnum);
getchar();
get_data(&data,num);
find_data(&data,out,qnum);
for(int i=0;i<qnum;i++)
{
printf("%d %d\n",out[i][0],out[i][1]);
}
system("pause");
}
void find_data(_data* data,int (*dout)[2],int qnum)
{
char temp[20];
int j,id=0,z=0;
int similarity=0;
_data* tdata=data;
for(int i=0;i<qnum;i++)
{
scanf("%s",temp);
for(j=0;j<18;j++)
{
id=temp[j]-'0';
if(tdata->amount[id])
tdata=tdata->next[id];
else
{
for(z=0;z<10;z++)
{
similarity+=tdata->amount[z];
}
(*dout)[0]=j;
(*dout)[1]=similarity;
dout++;
//printf("%d %d\n",j,similarity);
break;
}
}
tdata=data;
similarity=0;
}
}

void get_data(_data* data,int num)
{
char temp[20];
int j=0,id=0;
_data* tdata=data;
for(int i=0;i<num;i++)
{
scanf("%s",temp);
for(j=0;j<18;j++)
{
id=temp[j]-'0';
if(tdata->next[id]==NULL)
{
tdata->next[id]=new_data();
}
tdata->amount[id]++;
tdata=tdata->next[id];
}
tdata=data;
}
}

_data* new_data(void)
{
_data* new=(_data*)malloc(sizeof(_data));
_data** temp=new->next;
int* temp2=new->amount;
temp[0]=NULL;
temp[1]=NULL;
temp[2]=NULL;
temp[3]=NULL;
temp[4]=NULL;
temp[5]=NULL;
temp[6]=NULL;
temp[7]=NULL;
temp[8]=NULL;
temp[9]=NULL;
temp2[0]=0;
temp2[1]=0;
temp2[2]=0;
temp2[3]=0;
temp2[4]=0;
temp2[5]=0;
temp2[6]=0;
temp2[7]=0;
temp2[8]=0;
temp2[9]=0;
return new;
}

发表于 2021-09-27 22:14:14 回复(0)

能干的四郎不服输

哈希表来剔除前缀不一致的字符串，但是超时
#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")

发表于 2023-07-27 10:32:23 回复(0)

Python

一起学算法

这道题用 Python 能过吗？

发表于 2021-08-19 20:57:10 回复(0)

牛客479854335号

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;
    }


}

发表于 2021-08-08 10:10:41 回复(1)

C++

头文字F

利用红黑树map的key值有序特性，进行前后查找

#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;
}

发表于 2021-08-04 10:16:51 回复(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();
    }


}

发表于 2021-07-29 19:00:53 回复(0)

23届-谭江晓

#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;
}

发表于 2021-07-17 13:37:17 回复(0)

mawlek

前缀树

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<>();
        }
        
    }
}

编辑于 2021-07-08 17:23:41 回复(0)