(B卷,100分)- 增强的strstr（Java & JS & Python）

题目描述

C 语言有一个库函数： char *strstr(const char *haystack, const char *needle) ，实现在字符串 haystack 中查找第一次出现字符串 needle 的位置，如果未找到则返回 null。

现要求实现一个strstr的增强函数，可以使用带可选段的字符串来模糊查询，与strstr一样返回首次查找到的字符串位置。

可选段使用“[]”标识，表示该位置是可选段中任意一个字符即可满足匹配条件。比如“a[bc]”表示可以匹配“ab”或“ac”。

注意目标字符串中可选段可能出现多次。

输入描述

与strstr函数一样，输入参数是两个字符串指针，分别是源字符串和目标字符串。

输出描述

与strstr函数不同，返回的是源字符串中，匹配子字符串相对于源字符串地址的偏移（从0开始算），如果没有匹配返回-1。

补充说明：源字符串中必定不包含‘[]’；目标字符串中‘[]’必定成对出现，且不会出现嵌套。

输入的字符串长度在[1,100]之间。

用例

题目解析

本题最简单的解题策略是套皮正则表达式。

即将第二行输入的目标串直接当成正则表达式使用，因为其中[]的逻辑，刚好就是正则表达式“字符组”的功能。

根据考友反馈，本题输入的目标字符串中可能存在其他正则元字符，因此套皮正则表达式解法的结果可能会受到影响，实际考试套皮正则表达式可以拿95%通过率。

本题可以使用另一种比较稳健的解法，即将目标串分层，比如目标串 b[cd]，相当于两层：

• 第一层可选字符是：b
• 第二层可选字符是：cd

然后利用滑窗，滑窗长度就是目标串的层数，去在源字符串中滑动匹配，比如

滑窗解法

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  const src = await readline();
  const tar = await readline();

  // 将tar字符串转化为levels多层结构，转化逻辑为：tar字符串中，每个[]包含的所有字符作为一层，未被[]包含的单个字符作为一层
  const levels = [];

  // level用于记录[]中的字符
  let level = new Set();
  let isOpen = false;

  for (let c of tar) {
    switch (c) {
      case "[":
        isOpen = true;
        break;
      case "]":
        isOpen = false;
        levels.push(level);
        level = new Set();
        break;
      default:
        if (isOpen) {
          level.add(c);
        } else {
          levels.push(new Set([c]));
        }
    }
  }

  console.log(indexOf());

  function indexOf() {
    // 滑动匹配levels.length长度的子串
    for (let i = 0; i <= src.length - levels.length; i++) {
      let isFind = true;

      for (let j = 0; j < levels.length; j++) {
        if (!levels[j].has(src[i + j])) {
          isFind = false;
          break;
        }
      }

      if (isFind) {
        return i;
      }
    }

    return -1;
  }
})();

Java算法源码

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;

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

    String src = sc.nextLine();
    String tar = sc.nextLine();

    System.out.println(getResult(src, tar));
  }

  public static int getResult(String src, String tar) {
    // 将tar字符串转化为levels多层结构，转化逻辑为：tar字符串中，每个[]包含的所有字符作为一层，未被[]包含的单个字符作为一层
    ArrayList<HashSet<Character>> levels = new ArrayList<>();

    // level用于记录[]中的字符
    HashSet<Character> level = new HashSet<>();
    boolean isOpen = false;

    for (int i = 0; i < tar.length(); i++) {
      char c = tar.charAt(i);

      switch (c) {
        case '[':
          isOpen = true;
          break;
        case ']':
          isOpen = false;
          levels.add(level);
          level = new HashSet<>();
          break;
        default:
          if (isOpen) {
            level.add(c);
          } else {
            HashSet<Character> tmp = new HashSet<>();
            tmp.add(c);
            levels.add(tmp);
          }
      }
    }

    return indexOf(src, levels);
  }

  public static int indexOf(String src, ArrayList<HashSet<Character>> levels) {
    // 滑动匹配levels.length长度的子串
    for (int i = 0; i <= src.length() - levels.size(); i++) {
      boolean isFind = true;

      for (int j = 0; j < levels.size(); j++) {
        if (!levels.get(j).contains(src.charAt(i + j))) {
          isFind = false;
          break;
        }
      }

      if (isFind) return i;
    }

    return -1;
  }
}

Python算法源码

# 输入获取
src = input()
tar = input()


def indexOf(levels):
    # 滑动匹配levels.length长度的子串
    for i in range(len(src) - len(levels) + 1):
        isFind = True

        for j in range(len(levels)):
            if src[i + j] not in levels[j]:
                isFind = False
                break

        if isFind:
            return i

    return -1


# 核心代码
def getResult():
    # 将tar字符串转化为levels多层结构，转化逻辑为：tar字符串中，每个[]包含的所有字符作为一层，未被[]包含的单个字符作为一层
    levels = []

    # level用于记录[]中的字符
    level = set()
    isOpen = False

    for c in tar:
        if c == '[':
            isOpen = True
        elif c == ']':
            isOpen = False
            levels.append(level)
            level = set()
        else:
            if isOpen:
                level.add(c)
            else:
                levels.append({c})

    return indexOf(levels)


# 算法调用
print(getResult())

正则解法

JS算法源码

/* 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) {
    console.log(getResult(lines[0], lines[1]));
    lines.length = 0;
  }
});

function getResult(src, tar) {
  const res = new RegExp(tar).exec(src);

  if (res && res.length > 0) {
    return src.indexOf(res[0]);
  } else {
    return -1;
  }
}

Java算法源码

import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

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

    String src = sc.nextLine();
    String tar = sc.nextLine();

    System.out.println(getResult(src, tar));
  }

  public static int getResult(String src, String tar) {
    Matcher matcher = Pattern.compile(tar).matcher(src);

    if (matcher.find()) {
      return src.indexOf(matcher.group());
    } else {
      return -1;
    }
  }
}

Python算法源码

# 输入获取
import re

src = input()
tar = input()


# 核心代码
def getResult():
    res = re.search(tar, src)

    if res is None:
        return -1
    else:
        return res.start()


# 算法调用
print(getResult())