2023A卷，知识图谱新词挖掘

👨‍⚕️主页： gis分享者
👨‍⚕️感谢各位大佬 点赞👍 收藏⭐ 留言📝 加关注✅!
👨‍⚕️收录于专栏：华为OD面试

一、🍀前言

2023A卷，知识图谱新词挖掘。

1.1 ☘️题目详情

题目：

小华负责公司知识图谱产品，现在要通过新词挖掘完善知识图谱。新词挖掘：给出一个待挖掘文本内容字符串content和一个词的字符串word，找到content中所有word的新词。新词：使用词word的字符排列形成的字符串。请帮小华实现新词挖掘，返回发现的新词的数量。

输入：

第一行输入为待挖掘的文本内容content；第二行输入为词word。

输出：

在中找到的所有word的新词的数量。

备注：

0 ≤ content.length ≤ 10000000；1 ≤ word.length ≤ 2000

示例一：

// 输入qweebaewqd qwe// 输出2// 说明 起始索引等于 0 的子串是 qwe, 它是 word的新词。起始索引等于 6 的子串是 ewq, 它是 word的新词。

示例二：

// 输入AASW// 输出1// 说明 需要把一个 A 更换成 D，这样可以得到 ADSW 或者 DASW。

示例三：

// 输入abab ab// 输出3// 说明 起始索引等于 0 的子串是 ab, 它是 word 的新词。起始索引等于 1 的子串是 ba, 它是 word 的新词。起始索引等于 2 的子串是 ab, 它是 word 的新词。

1.2 ☘️参考解题答案

解题思路

由于content 中的子串都需要和单词 word 进行比较，所以长度不等于rd 的子串必然不符合要求，因此我们可以使用一个长度为 1en(word)的固定长度滑裔来完成新词挖掘过程。
新司的定义是使用词 wrd 的字符排列形成的字符串，显然和字符在子串中的出现频率有关，很容易想到使用哈希表counter()来完成元素频率统计。

滑窗三问

**Q1:**对于每一个右指针 right 所指的元素 right_ch ，做什么操作?
**Q2:**什么时候要令左指针 left 右移?对于 left所指的元素 left_ch ，要做什么操作?
**Q3:**什么时候进行 ans 的更新?如何更新?

滑窗三答

**A1:**将right_ch 在窗囗对应哈希表 cnt_windows 中的统计次数 +1
**A2:**将left_ch 在窗囗对应哈希表 cnt windows 中的统计次数 -1，如果left_ch 的出现次数降为0，则删除left_ch 的键值对。
**A3:**如果cnt_windows == cnt_word，更新答案变量

Python实现：

# 题目：2023Q1A-知识图谱新词挖掘# 分值：100# 作者：闭着眼睛学数理化# 算法：固定滑窗# 代码看不懂的地方，请直接在群上提问fromcollectionsimportCounter content=input()word=input()# 获得固定滑窗的长度，为单词word的长度k=len(word)# 初始化word对应的哈希表cnt_word=Counter(word)# 初始化第一个固定滑窗对应的哈希表cnt_windows=Counter(content[:k])# 考虑第一个滑窗的情况ans=int(cnt_windows==cnt_word)forright,right_chinenumerate(content[k:],k):# Q1：对于每一个右指针right所指的元素right_ch，做什么操作？# A1：将right_ch在窗口中的统计次数+1cnt_windows[right_ch]+=1# Q2：什么时候要令左指针left右移？# 对于left所指的元素left_ch，要做什么操作？# A2：在固定滑窗中，left始终为right-N# 将left_ch在窗口中的统计次数-1left=right-k left_ch=content[left]cnt_windows[left_ch]-=1ifcnt_windows[left_ch]==0:delcnt_windows[left_ch]# Q3：什么时候进行ans的更新？# A3：做完cnt_windows的更新后，取其中最大值和当前ans比较并更新ifcnt_windows==cnt_word:ans+=1print(ans)

c++实现：

#include<iostream>#include<string>#include<unordered_map>usingnamespacestd;intmain(){string content;string word;getline(cin,content);getline(cin,word);intk=word.size();unordered_map<char,int>cntWord;for(charc:word){cntWord[c]++;}unordered_map<char,int>cntWindows;intans=0;for(intright=0;right<k;right++){charrightCh=content[right];cntWindows[rightCh]++;}if(cntWindows==cntWord){ans++;}for(intright=k;right<content.size();right++){charrightCh=content[right];cntWindows[rightCh]++;intleft=right-k;charleftCh=content[left];cntWindows[leftCh]--;if(cntWindows[leftCh]==0){cntWindows.erase(leftCh);}if(cntWindows==cntWord){ans++;}}cout<<ans<<endl;return0;}

java实现：

importjava.util.Scanner;importjava.util.HashMap;importjava.util.Map;publicclassMain{publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);Stringcontent=scanner.nextLine();Stringword=scanner.nextLine();intk=word.length();Map<Character,Integer>cntWord=newHashMap<>();for(charc:word.toCharArray()){cntWord.put(c,cntWord.getOrDefault(c,0)+1);}Map<Character,Integer>cntWindows=newHashMap<>();intans=0;for(intright=0;right<k;right++){charrightCh=content.charAt(right);cntWindows.put(rightCh,cntWindows.getOrDefault(rightCh,0)+1);}if(cntWindows.equals(cntWord)){ans++;}for(intright=k;right<content.length();right++){charrightCh=content.charAt(right);cntWindows.put(rightCh,cntWindows.getOrDefault(rightCh,0)+1);intleft=right-k;charleftCh=content.charAt(left);cntWindows.put(leftCh,cntWindows.get(leftCh)-1);if(cntWindows.get(leftCh)==0){cntWindows.remove(leftCh);}if(cntWindows.equals(cntWord)){ans++;}}System.out.println(ans);}}

javaScript：

/* JavaScript Node ACM模式 控制台输入获取 */constreadline=require("readline");constrl=readline.createInterface({input:process.stdin,output:process.stdout,});constlines=[];rl.on("line",(line)=>{lines.push(line);if(lines.length===2){constcontent=lines[0];constword=lines[1];console.log(getResult(content,word));lines.length=0;}});functiongetResult(content,word){if(content.length<word.length){return0;}constsorted_word=[...word].sort().join("");letans=0;letmaxI=content.length-word.length;for(leti=0;i<=maxI;i++){constsorted_substr=[...content.slice(i,i+word.length)].sort().join("");if(sorted_substr===sorted_word)ans++;}returnans;}

时空复杂度

时间复杂度:：0(N)。仅需一次遍历数组。
空间复杂度：0(N)。哈希表所占用空间。