知识图谱新词挖掘1
题目描述：
代码语言：javascript复制 小华负责公司知识图谱产品，现在要通过新词挖掘完善知识图谱。
新词挖掘：给出一个待挖掘文本内容字符串Content和一个词的字符串word，找到content中所有word的新词。
新词：使用词word的字符串排列形成的字符串。
请帮小华实现新词挖掘，返回发现的新词的数量。
输入描述：第一行输入待挖掘的文本内容content；
第二行输入为词word；
输出描述：在content中找到的所有word的新词的数量。
补充说明：0 <= content的长度 <= 10000000;
1 <= word的长度 <= 2000
示例1
输入：qweebaewqd
qwe
输出：2
说明：起始索引等于0的子串是"qwe",它是word的新词。
起始索引等于6的子串是"ewq"，它是word的新词。
示例2
输入：abab
ab
输出：3
说明：起始索引等于0的子串"ab"，它是 word的新词.
起始索引等于1的子串"ba"，它是 word的新词。
起始索引等于2的字串"ab"，它是 word的新词。滑动窗口解法
可以采用滑动窗口算法，这道题和力扣76题.最小覆盖字串以及力扣567题.字符串的排列很类似。 C 实现代码如下：
代码语言：javascript复制#include<iostream>
#include<unordered_map>
#include <string>
using namespace std;
// 滑动窗口算法
int slidingWindow(const string &content, const string &word)
{
if (content.size() < word.size()) {
return 0;
}
if (word.empty()) {
return 0;
}
unordered_map<char, int> need, window;
for (char c : word) {
need[c] ;
}
int resultCnt = 0;
int left = 0, right = 0;
int valid = 0;
// 遍历content字符串
while (right < content.size()) {
// a 是将要移入窗口的字符
char a = content[right];
// 增大窗口
right ;
// 进行窗口内数据的一系列更新
if (need.count(a)) {
window[a] ;
// 如果content中的某个字符个数和word中的个数相同，则valid有效字符计数器加1
if (need[a] == window[a]) {
valid ;
}
}
// 此处可以 debug 窗口的位置
//printf("window: [%d, %d)n", left, right);
// 判断左侧窗口是否需要收缩
// 本题移动left缩小窗口的时机是窗口大小大于word.size()时，因为排列（新词），显然长度是一样的
while (right - left >= word.size()) {
// 在这里更新找到新词的计数器，当valid == need.size()时，说明窗口包含合格的新词，此时找到一个新词
if (valid == need.size()) {
resultCnt ;
}
// d 是将要移出窗口的字符
char d = content[left];
// 缩小窗口
left ;
// 进行窗口的一系列更新
if (need.count(d)) {
if (window[d] == need[d]) {
valid--;
}
window[d]--;
}
}
}
return resultCnt;
}
int main()
{
//输入处理
string content;
string word;
while (cin >> content >> word) {
std::cout << slidingWindow(content, word) << std::endl;
}
return 0;
}
