【固定滑窗】2023A-知识图谱新词挖掘

题目描述与示例

本题练习地址：https://www.algomooc.com/problem/P3252

题目描述

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

输入描述

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

输出描述

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

备注

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

示例一

输入

qweebaewqd
qwe

输出

说明

起始索引等于 0 的子串是 qwe, 它是 word的新词。起始索引等于 6 的子串是 ewq, 它是 word的新词。

示例二

输入

abab
ab

输出

说明

起始索引等于 0 的子串是 ab, 它是 word 的新词。起始索引等于 1 的子串是 ba, 它是 word 的新词。起始索引等于 2 的子串是 ab, 它是 word 的新词。

解题思路

由于content中的子串都需要和单词word进行比较，所以长度不等于word的子串必然不符合要求。因此我们可以使用一个长度为len(word)的固定长度滑窗来完成新词挖掘过程。

新词的定义是使用词word的字符排列形成的字符串，显然和字符在子串中的出现频率有关，很容易想到使用哈希表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
# 作者：闭着眼睛学数理化
# 算法：固定滑窗
# 代码看不懂的地方，请直接在群上提问


from collections import Counter

content = input()
word = input()

# 获得固定滑窗的长度，为单词word的长度
k = len(word)
# 初始化word对应的哈希表
cnt_word = Counter(word)
# 初始化第一个固定滑窗对应的哈希表
cnt_windows = Counter(content[:k])

# 考虑第一个滑窗的情况
ans = int(cnt_windows == cnt_word)

for right, right_ch in enumerate(content[k:], k):
    # Q1：对于每一个右指针right所指的元素right_ch，做什么操作？
    # A1：将right_ch在窗口中的统计次数+1
    cnt_windows[right_ch] += 1

    # Q2：什么时候要令左指针left右移？
    # 对于left所指的元素left_ch，要做什么操作？
    # A2：在固定滑窗中，left始终为right-N
    # 将left_ch在窗口中的统计次数-1
    left = right - k
    left_ch = content[left]
    cnt_windows[left_ch] -= 1
    if cnt_windows[left_ch] == 0:
        del cnt_windows[left_ch]

    # Q3：什么时候进行ans的更新？
    # A3：做完cnt_windows的更新后，取其中最大值和当前ans比较并更新
    if cnt_windows == cnt_word:
        ans += 1

print(ans)

Java

import java.util.Scanner;
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String content = scanner.nextLine();
        String word = scanner.nextLine();

        int k = word.length();
        Map<Character, Integer> cntWord = new HashMap<>();
        for (char c : word.toCharArray()) {
            cntWord.put(c, cntWord.getOrDefault(c, 0) + 1);
        }

        Map<Character, Integer> cntWindows = new HashMap<>();
        int ans = 0;

        for (int right = 0; right < k; right++) {
            char rightCh = content.charAt(right);
            cntWindows.put(rightCh, cntWindows.getOrDefault(rightCh, 0) + 1);
        }

        if (cntWindows.equals(cntWord)) {
            ans++;
        }

        for (int right = k; right < content.length(); right++) {
            char rightCh = content.charAt(right);
            cntWindows.put(rightCh, cntWindows.getOrDefault(rightCh, 0) + 1);

            int left = right - k;
            char leftCh = 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);
    }
}

C++

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    string content;
    string word;
    getline(cin, content);
    getline(cin, word);

    int k = word.size();
    unordered_map<char, int> cntWord;
    for (char c : word) {
        cntWord[c]++;
    }

    unordered_map<char, int> cntWindows;
    int ans = 0;

    for (int right = 0; right < k; right++) {
        char rightCh = content[right];
        cntWindows[rightCh]++;
    }

    if (cntWindows == cntWord) {
        ans++;
    }

    for (int right = k; right < content.size(); right++) {
        char rightCh = content[right];
        cntWindows[rightCh]++;

        int left = right - k;
        char leftCh = content[left];
        cntWindows[leftCh]--;
        if (cntWindows[leftCh] == 0) {
            cntWindows.erase(leftCh);
        }

        if (cntWindows == cntWord) {
            ans++;
        }
    }

    cout << ans << endl;
    return 0;
}

JavaScript

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");
 
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
 
const lines = [];
rl.on("line", (line) => {
  lines.push(line);
 
  if (lines.length === 2) {
    const content = lines[0];
    const word = lines[1];
 
    console.log(getResult(content, word));
    lines.length = 0;
  }
});
 
function getResult(content, word) {
  if (content.length < word.length) {
    return 0;
  }
 
  const sorted_word = [...word].sort().join("");
 
  let ans = 0;
  let maxI = content.length - word.length;
  for (let i = 0; i <= maxI; i++) {
    const sorted_substr = [...content.slice(i, i + word.length)]
      .sort()
      .join("");
 
    if (sorted_substr === sorted_word) ans++;
  }
 
  return ans;
}

时空复杂度

时间复杂度：O(N)。仅需一次遍历数组。

空间复杂度：O(N)。哈希表所占用空间。